1

I need to solve the recurrence

T(n) = 2T(n1/2) + 1

I need to find the asymptotic time complexity. I'm using the recursion tree method but I'm getting stuck. I know the answer is Θ(log n), but I'm not sure how to arrive at this. How do you solve this recurrence?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Mahe
  • 5
  • 1
  • 1
  • 6
  • yes the recurrence is what you said ! – Mahe Jul 18 '16 at 18:20
  • 1
    What's the stop clause? – amit Jul 18 '16 at 19:19
  • I'm voting to close this question as off-topic because this is not a programming question, and actually belongs on [Mathematics](http://math.stackexchange.com/), not Stack Overflow. – Michael Gaskill Jul 18 '16 at 20:31
  • @MichaelGaskill I think this belongs here, but if it didn't, it would belong on CS, not Mathematics. – intboolstring Jul 18 '16 at 20:44
  • @intboolstring I agree with your suggestion of [Computer Science](http://cs.stackexchange.com), but I think it really is off-topic for Stack Overflow. If you read the [tour](/tour), there's nothing about this question that is suited to SO. – Michael Gaskill Jul 18 '16 at 21:01
  • @MichaelGaskill Alright. If you believe that asking about recurrence relationships is off-topic for Stack Overflow, I would suggest making a meta [tag:burninate-request] for [tag:recurrence-relation]. – intboolstring Jul 18 '16 at 21:04

3 Answers3

5

If you see a recurrence T(n) where one of the terms depends on the square root of the input size, it's often useful to define a new recurrence

S(k) = T(2k)

since the resulting recurrence in k is often a lot easier to work with than the corresponding recurrence in n. In our case, we have

S(k) = T(2k)

= 2T(√(2k)) + 1

= 2T(2k/2) + 1

= 2S(k / 2) + 1

Notice that we now have a recurrence that matches the form expected by the master theorem (and that generally is much easier to work with than the original one). We can solve this recurrence to S(k) = Θ(k) via a number of different techniques.

Since we know that S(k) = Θ(k), what can we say about T(n)? Well, assuming that we're okay fudging things that aren't exact powers of two, we can say that T(n) ≈ S(lg n), since S(lg n) = T(2lg n) = T(n). Therefore, we get that

T(n) = S(lg n) = Θ(lg n)

so T(n) = Θ(lg n).

Here's another way to arrive at this result that's less mathematical and more intuitive. Imagine the shape of the recursion tree that's formed by expanding the original recurrence T(n). At the top level, we have one call of size n doing 1 work. At the next level we have two calls of size 2√n for a total of 2 work. At the level below that are four calls of size 4√n for a total of 4 work. More generally, at level k, we have 2k calls each doing 2k√n work. The recursion terminates when n gets sufficiently small (say, n = 2), which happens at some level k. At that point, the total work done will have been

1 + 2 + 4 + 8 + 16 + ... + 2k = 2(2k) - 1.

If we can solve for k, we'll know how much total work is done. Notice that the recursion stops when the input drops to size 2, which means that the k we want is one where 2k√n = 2. Solving for k, we see that

2k√n = 2

n = 22k

lg lg n = k

In general, if you see something shrinking by a square root factor, you should expect that the number of iterations before the term drops to a constant is O(log log n). Therefore, the total work done is 2(2lg lg n) + 1 = 2 lg n - 1 = Θ(lg n), as before.

Community
  • 1
  • 1
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • so it _doesn't_ depend on the termination condition? –  Jul 18 '16 at 20:52
  • @willywonkadailyblah In an asymptotic sense, assuming the termination condition is a fixed constant (both of when it triggers and what it evaluates to), no, it doesn't matter. It shaves at most a constant amount of work off the recursion tree or amplifies the total work done in the tree by a constant factor. – templatetypedef Jul 18 '16 at 20:57
  • Thankyou very much... the solution is very helpful ! – Mahe Jul 19 '16 at 06:01
  • Hi, I' m not getting one thing,please if you could explain that how the series 1 + 2 + 4 + 8 + 16 + ... + 2k is resulting to the value 2(2^k) - 1? – Mahe Jul 19 '16 at 07:35
  • It's the sum of the geometric series 2^0 + 2^1 + 2^2 + ... + 2^k. It's worth committing the formula for the sum of a geometric series - and this series in particular - to memory. – templatetypedef Jul 19 '16 at 13:50
  • @templatetypedef can you please ellaborate 2(2^(lg lg n)) + 1 = 2 lg n - 1 = Θ(lg n), – laura Oct 10 '17 at 18:59
  • 1
    @Laura The key step here is (2^(lg lg n)) = lg n, which is true because 2^(lg x) = x for any x. Does that help? – templatetypedef Oct 10 '17 at 19:00
  • Ahhh, i missed that , i know 3^(log base(2) n)=n^(log base(2) 3) ..thanks – laura Oct 10 '17 at 19:04
1

Let us make the substitution enter image description here

Then

enter image description here

Where N is the number of terms before the series terminates.

But what is N? This depends on the answer to amit's comment. Let assume that non-integer values are allowed for n in T(n), and that T terminates (= 0) for n < C, for some constant C > 1.

Then we need

![enter image description here

So the complexity is also dependent on C:

enter image description here

EDIT: Data to support my answer:

  • graph of T against log n, C = 1.5:

enter image description here

  • graph of T against - log C, n = 2^64:

enter image description here

As you can see, both are linear.

1

Using Recursion tree method, you can solve as follows: follow this link

shubham kumar
  • 11
  • 1
  • While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. – Til Apr 12 '19 at 11:30
  • Can you help me with a more difficult example using same recursion tree method? Specifically after I got 2^k-1. Here is recurrence: T\left(n\right)=2T\left(\sqrt{n-1}+2\right)+1 – Viktor Vostrikov Apr 13 '19 at 09:57