Question

Use a recursion tree to determine a good asymptotic upper bound on the recurrence ?(?) = 3?(?/3) + ?. Use the substitution method to verify your answer.

Answer 1

Solution:

Given,

=>T(n) = 3T(n/3) + n

Explanation:

Solving recurrence relation using recursion tree:

=>Cost at each level of tree is presented.

=>Total cost can be found by summing up the costs of all the levels of recursion tree.

Verification using substitution method:

=>T(n) = 3T(n/3) + n...(1)

=>T(n/3) = 3T*n/3^2) + n/3...(2)

From (1) and (2)

=>T(n) = 3^2T(n/3^2) + n + n

and so on.

=>T(n) = 3^kT(n/3^k) + n + n + .....k times

=>T(n) = 3^kT(n/3^k) + n*k...(3)

=>Let say T(1) = 1

=>n/3^k = 1

=>n = 3^k

Taking log both sides on base 3

=>k = log₃(n)..(4)

From (3) and (4)

=>T(n) = 3^log₃(n)*1 + n*log₃(n)

=>T(n) = n + n*log₃(n)

=>Hence T(n) = O(n*log(n))

I have explained each and every part with the help of statements as well as image attached to it.