Question

Solve or estimate this recurrence relation T(n) = 2 T(n/3) + T(n/2) + n

Answer 1

Estimation :

1) Let us assume T(n) = 3*T(n/3) +n ;

2) Let us assume T(n)= 3*T(n/2) + n

From Masters Theorem

1) We get T(n)= Theta(nlogn)

2)We get T(n) = Theta(n^1.58)

So our answer will be in the range n^1.0000001 < T(n) < n^1.58

Solving:

For solving let us assume T(n)=O(n^k) that implies T(n) <= c*n^k for all n>n0 and k>1.

substituting the above equation in our original recurrence relation we get

1 = 2/3^k + 1/2^k + n/n^k (we know k>1 so n/n^k ->0 for large values of n),
so we get 1 = 2/3^k + 1/2^k ,  by solving we get k value as nearly 1.167

So T(n)=O(n^1.1674) is our answer.

Answer 2

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

1/3 + 1/3 + 1/2 = 7/6 

since it's greater than 1, [ Shortcut Method ]

Time complexity = O(n logn)

Answer 3

Use the Akra-Bazzi method: