Question

Solve the recurrence equation.

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

T(1) = C

Answer 1

The above equation is of the form

T(n) = a* T(n/b) + f(n)

Here a = 3, b = 3 and f(n) = C*n

This recurrence relation can be solved by Master's theorem.

It has three cases. The following are the three cases :

case 1:

If f(n) = Θ(n^k) where k <   then T(n) = Θ(n  ^ ())

case 2:

If f(n) = Θ(n^k) where k =   then T(n) = Θ((n^k)*)

case 3;

If f(n) = Θ(n^k) where k > then T(n) = Θ( f(n) )

In our case a = 3 , b = 3 , k = 1

case 2 applies in our case where k =1 and also equals 1.

T(n) = Θ((n)*))

Another solution:

T(n) = 3 T(n/3) + C*n

T(n/3) = 3 T(n/9) + C*n/3

substituting T(n/3) in the first equation

T(n) = 3( 3 T(n/9) + C *n/3 ) + C* n

= 9 T(n/9) + 2* C*n ( equation 2)

T(n/9) = 3 T(n/27) + c*n/9

substituting T(n/9) in equation (2)

T(n) = 9 ( 3 T(n/27) + C*n/9) + 2 *C*n

= 27 T(n/27) + C*n + 2 * C* n

= 27 T(n) + 3 * C * n  

T(n) = (3 ^ k) * T( n / ( 3 ^k ) ) + k * C * n

Replace k with

T(1) = C

T(n) = 3^( ) *T( n / ( 3 ^ ) ) + k * C * n

3^( ) will equal to n.

n / ( 3 ^ ) will equal to 1.

T(n) = n * T(1 )  +  * C* n

T(n) = n*C +   * C* n

T(n) = O( n * )

Hence O( n *   )