Solve the following recurrence Tn 3Tn4 Tn2 nSolution give

Solve the following recurrence:

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

Solution

-> given recurrence is T(n) = 3T(n/4) + T(n/2) + n

=> T(n) = 3[3 T(n/16) + T(n/8) + n/4 ] + 3T(n/8) + T(n/4) + n/2 + n

=> T(n) = 9T(n/16) + 3T(n/8) + 3(n/4) +  3T(n/8) + T(n/4) + n/2 + n

=> T(n) = 9T(n/16) + 6T(n/8) + T(n/4)  + 3(n/4) + n/2 + n

=> T(n) = 9[ 3T(n/64) + T(n/32) + n/16 ] + 6[3 T(n/32) + T(n/16) + n/8 ] +   3T(n/16) + T(n/8) + n/4 ] + (5n)/4 + n

=> T(n) = 27T(n/64) +27 T(n/32) + 9T(n/16) + T (n/8) + 9n/16 + 6n/8 + n/4 + 5n/4 + n

=> T(n) = 27T(n/64) +27 T(n/32) + 24 T(n/16) + 3 T (n/8) + 25n/16 + 5n/4 + n

=> T(n) = 3³T(n/4³) +27 T(n/32) + 24 T(n/16) + 3 T (n/8) + n[1 + 5/4 + (5/4)² ]

: : : : :

: : : : :

( since length of recursion = log 4/3 n because large value of recurrence is first segment in given relation and not balancing recurrently. so (logn) for the recurrence 27T(n/64) +27 T(n/32) + 24 T(n/16) + 3 T (n/8)

and n for the recurrence  n[1 + 5/4 + (5/4)² + (5/4)³ +. .. . . .] because [1 + 5/4 + (5/4)² + (5/4)³ +. .. . . .] is constant value)

T(n) = O(n log n).