in Algorithms
601 views
1 vote
1 vote

T(n) =  a1 T(n/b) + a2 T(n/b)

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

in Algorithms
by
601 views

4 Comments

 T1(n) =a1 T(n/b1

 T2(n) =a2 T(n/b2

T(n) = max( T1(n) + T2(n) ) .

for your example it should be $\Theta$( n ).

0
0
How did u get that O(n) . please explain the steps
0
0

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

       = T(n/16) + n/4 + n

       = T(n/64)  + n/16 + n/4 + n.

 .

.

T(n) = T(1) + n/log4 n + ...... +  n/16 + n/4 + n.

      =  n { 1 + 1/4 + 1/16 + ..... (log4 n)th term )

      = O(n).

Similarly do for others...

0
0
just draw a recurrence tree.. it easy ...
0
0

Please log in or register to answer this question.