Computer Algorithms I Problems

I need help in solving the 5 problems in the hw.

Homework Assignment
Computer Algorithms I
Problem 1. Draw a tree for the recurrence T (n) = T ( n2 ) + T ( n4 ) + n and determine the
appropriate guess for the solution to the recurrence. Do not prove your solution, just determine it based on the recursion tree.
Problem 2. Using method of your choice, determine and prove the solution to the following
recurrences.
1. T (n) = 3T ( n3 ) +
n
2
2. T (n) = 2T ( n4 ) + n0.51
3. T (n) = 4T ( n2 ) + n2
4. T (n) = 4T ( n2 ) + n
5. T (n) = 7T ( n3 ) + n2
Problem 3. The Case 3 of the Master Theorem carries a regularity condition af ( nb ) ≤
cf (n) for some constant c < 1. Find a value for the constants a ≥ 1 and b > 1, and a
function f (n) that satisfy all the conditions in Case 3 of the Mater Theorem, except the
regularity condition.
Problem 4. Determine the height of an n-element heap and prove its correctness.
Problem 5. Consider the recurrence T (n) = T (n − 1) + Θ(n). Prove that T(n) is Θ(n2).
2