retagged by
481 views

1 Answer

2 votes
2 votes

Given , 

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

So in recursion tree method we calculate the cost of each level in the recursion tree and compare it with previous level..If the cost is less than that of previous level then we do not need to find the entire sum as it will be a decreasing G.P. series..So here ,

cost in 1st level  =  n2

cost in 2nd level  = (n/2)2 [ Due to branch T(n/2) ] +  (n/4)2

                          = 5n2 / 16 

So we can see here cost of 2nd level is less than 1st level..Hence it will form a decreasing G.P.

Hence 

T(n)     = Sum of costs at all levels

           = n2 [  1 + (5/16) + (5/16)2 ............. ]

           = O(n2 )

Hence T(n)  =  O(n2)

Related questions

2 votes
2 votes
1 answer
1
yuyutsu asked Jun 22, 2022
603 views
T(n) = 5T(n/3) + T(2n/3) + 1.My answer is BigOmega(n) BigO(n). Am I right? This is a question I found on cs.stackexchange.
1 votes
1 votes
2 answers
2