1

This recurrence:

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

It does not appear to be solvable with Master theorem. It also does not appear to be solvable with Akra-Bazzi. Even if I set n = 2^k so that T(2^k) = 2^(k/2) * T(2^(k/2)) + 2^k and then have S(k) = T(2^k) it becomes S(n) = 2^(n/2) * S(n/2) + 2^n but the multiplier is not constant, so changing variables doesn't work either.

I am not sure how to derive the closed form, or the time complexity, of this recurrence, if it had been given to me in an interview. What would you do?

user1952500
  • 6,611
  • 3
  • 24
  • 37
AJJ
  • 2,004
  • 4
  • 28
  • 42

2 Answers2

2

I have not used any of the common techniques here.

Note that there is no base case. Let us consider T(a) = b where a and b are constants as the base case.

Dividing by 'n', we get: T(n) / n = T(sqrt(n)) / sqrt(n) + 1

Use g(k) = T(k) / k

So g(n) = g(sqrt(n)) + 1

This basically means g(n) is the number of times we can take the sqrt(n) before which we reach the constant base case a.

That means there is a k such that n^(1/2^k) >= a and n^(1/2^(k+1)) < a.

Let n^(1/2^k) = a => n = a^(2^k) => lg(n) = 2^k => lg(lg(n)) = k. Then g(n) = k + b = O(log(log(n))).

This means T(n) = n * O(log(log(n))) = O(n * log(log(n))). Substituting this into the original equation seems to make sense.

Verification: If you set the constant in the O() notation as 1 and let T(n) = n * lg(lg(n)) where lg(n) is log to base 2, we get

RHS = sqrt(n) * (sqrt(n) * lg(lg(sqrt(n)))) + n
     = n * lg(1/2 * (lg(n))) + n
     = n * (lg(lg(n)) - 1) + n
     = n * lg(lg(n)) - n + n
     = T(n)
     = LHS
user1952500
  • 6,611
  • 3
  • 24
  • 37
2

These type of recursions can be solved by unrolling the recursion, spotting the similarities between elements.

enter image description here

Now at some point the recursion will exhaust itself. This will happen if T(...) = T(a) = b. Any reasonable a will work, so I selected 2. Solving the equation n^(1/2^k) = 2 by taking log of both sides, you get: k = log(log(n)). Now substitute it back in your recursion:

enter image description here

Limit of 2^(-loglogn) is equal to 0 if n -> infinity, so the first element in summation is equal to b. The complexity is O(n * log log (n))

Take a look at some other sqrt recurrences:

Also no one would give this to you at the interview.

Community
  • 1
  • 1
Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
  • If you take logarithms to base `2`, `n^(2^(-lg(lg(n)))) = n^(1/(2^(lg(lg(n))))) = n^(1/(lg(n))) = n^log<2 to base n> = 2`, which is the constant. The same is true with some additional manipulation to any base and does not need a limit. – user1952500 Jan 18 '16 at 05:39
  • What kinds of recursions might I get, then? – AJJ Jan 18 '16 at 05:39
  • BTW why should nobody ask this at an interview ? There is no real need to compute this in particular but this could be the next step in analyzing a programming question. – user1952500 Jan 18 '16 at 05:40
  • Unrolling the recursion is how I solved it as well but wasn't sure if that was an acceptable technique – AJJ Jan 18 '16 at 05:41
  • 1
    @user1952500 because this kind of knowledge does not represent the average workload. How often do you need to solve similar recursion during your work. In case of my 5 years - 0 time. – Salvador Dali Jan 18 '16 at 05:51
  • 1
    @ArukaJ not only this is acceptable technique, this is the most universal technique. I have yet to see a recursion that can't be solved with unrolling. It will not be the most elegant solution (I agree that user's solution looks way nicer and way easier), but if the recursion would be `n * T(sqrt(n)) + ln(n)` the elegant substitution would not work – Salvador Dali Jan 18 '16 at 05:53
  • @SalvadorDali I agree that for the average workload the above knowledge does not make sense. However there are many graph algorithms that have this kind of complexity. Depending on the job description there may be a need to remember, if not then derive quickly, the answer to such recurrences. I have a decade in the systems side and the most intricate data structures I have needed to use are tries and huffman trees, so you can see how helpful the average is. – user1952500 Jan 18 '16 at 07:46