1

I know how to solve the recurrence relations using Master Method. Also I'm aware of how to solve the recurrences below:

T(n) = sqrt(n)*T(sqrt(n)) + n

T(n) = 2*T(sqrt(n)) + lg(n)

In the above two recurrences there is same amount of work at each level of the recursion tree. And there are a total of log log n levels in the recursion tree.

I'm having trouble in solving this one: T(n) = 4*T(sqrt(n)) + n

EDIT: Here n is a power of 2

5
  • 6
    I think this belongs on the theoretical CS stack exchange site
    – 0x1F602
    Nov 19, 2012 at 16:55
  • In any case, you simply keep "unraveling" the recurrence relation by substituting the original equation back in for T() and distributing. You do this until you observe a pattern, and then you define that pattern usually in terms of "k."
    – 0x1F602
    Nov 19, 2012 at 16:56
  • I have got the pattern but i could not solve it...!! Nov 19, 2012 at 17:12
  • I proceeded the same way as suggested by you. Nov 19, 2012 at 17:13
  • I'm voting to close this question as off-topic because it belongs on maths. Or one of the CS sites.
    – Brett Hale
    Mar 1, 2016 at 3:31

4 Answers 4

5

Suppose that n = 2^k. We have T(2^k) = 4*T(2^(k/2)) + 2^k. Let S(k) = T(2^k). We have S(k) = 4S(k/2) + 2^k. By using Mater Theorem, we get S(k) = O(2^k). Since S(k) = O(2^k) and S(k) = T(2^k), T(2^k) = O(2^k) which implies T(n) = O(n).

1
  • 1
    Can you really use the Master Theorem here though since the 2 inside the S(k/2) is not constant in this case?
    – rasen58
    Sep 6, 2017 at 15:05
1

I'm having trouble in solving this one: T(n) = 4*T(sqrt(n)) + n

EDIT: Here n is a power of 2

This edit is important. So lets say that the recurrence stops at 2.

So the question now is how deep the recursion tree is. Well, that is the number of times that you can take the square root of n before n gets sufficiently small (say, less than 2). If we write

n = 2lg n

then on each recursive call n will have its square root taken. This is equivalent to halving the above exponent, so after k iterations we have that

n1/(2k) = 2lg n/(2k)

We want to stop when this is less than 2, giving

2lg n/(2k) = 2

lg n/(2k) = 1

lg n = 2k

lg lg n = k

So after lg lg n iterations of square rooting the recursion stops. (source)

For each recursion we will have 4 new branches, the total of branches is 4 ^ (depth of the tree) therefore 4^(lg lg n).

EDIT:

enter image description here

Source

0
0
   T(n) = 4 T(sqrt(n)) + n
   4 [ 4 T(sqrt(sqrt(n) + n ] + n
   4^k * T(n^(1/2^k)) +kn because n is power of 2.
   4^k * T(2^(L/2^k)) +kn   [  Let n = 2^L , L= logn]
   4^k * T(2) +kn   [  Let L = 2^k,  k = logL = log log n]
   2^2k * c +kn
   L^2 * c + nloglogn 
   logn^2 * c + nloglogn
   = O(nloglogn)
0
T(n) = 4T(√n) + n 
suppose that (n = 2^m) . so we have :
T(2^m) = 4T(2^(m/2)) + (2^m)
now let name T(2^m) as S(m):
S(m) = 4S(m/2) + m . now with master Method we can solve this relation, and the answer is :
S(m) = Θ(m^2) 
now we step back to T(2^m):
T(2^m) = Θ((2^m)^2)
now we need m to solve our problem and we can get it from the second line and we have :
n = 2^m   =>   m=lgn 
and the problem solved .
T(n) = Θ((2^lgn)^2)
T(n) = Θ(n^2)
1
  • 2
    Could you please at least add a few words to help explain your answer?
    – Joey
    Apr 28, 2019 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.