Solving a recurrence T(n) = 2T(n/2) + sqrt(n) [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 8 years ago.

Improve this question

Need a little help! This is what I have so far using backward substitution:

T(n) = 2T(n/2) + sqrt(n), where T(1) = 1, and n = 2^k
T(n) = 2[2T(n/4) + sqrt(n/2)] + sqrt(n) = 2^2T(n/4) + 2sqrt(n/2) + sqrt(n)
T(n) = 2^2[2T(n/8) + sqrt(n/4)] + 2sqrt(n/2) + sqrt(n)
     = 2^3T(n/8) + 2^2sqrt(n/4) + 2sqrt(n/2) + sqrt(n)

In general

T(n) = 2^kT(1) + 2^(k-1) x sqrt(2^1) + 2^(k-2) x sqrt(2^2) + ... + 2^1 x sqrt(2^(k-1)) + sqrt(2^k)

Is this right so far? If it is, I can not figure out how to simplify it and reduce it down to a general formula.

I'm guessing something like this? Combining the terms

= 1 + 2^(k-(1/2)) + 2^(k-(2/2)) + 2^(k-(3/2)) + ... + 2^((k-1)/2) + 2^(k/2)

And this is where I'm stuck. Maybe a way to factor out a 2^k? Any help would be great, thanks!

Answer 1

You're half way there. The expression can be simplified to this:

Answer 2

If you want just a big-O solution, then Master Theorem is just fine.

If you want a exact equation for this, a recursion tree is good. like this:

The right hand-side is cost for every level, it's easy to find a general form for the cost, which is sqrt((2^h) * n). Then, sum up the cost you could get T(n).

1. According to Master Theorem, it's case 1, so O(n).
2. According to Recursion Tree, the exact form should be sqrt(n)*(sqrt(2n)-1)*(sqrt(2)+1), which corresponds with the big-O notation.

EDIT:

The recursion tree is just a visualized form of the so called backward substitution. If you sum up the right hand side, i.e. the cost, you could get the generalized form of T(n). All these methods could found in introduction to algorithm