$$T(n)= 2T(n/2) + \sqrt{n}$$
This recurrence was in a stackoverflow question, and I want to solve it without relying on the master method. The solution was given, but wolframAlpha gives a slightly different equation:
$$(1) \quad T(n)= n/2 + (1+\sqrt2)(n-\sqrt{n})$$
My Attempt
This was an image that one of the replier's had:
From the recursion tree, I get that the recursion is $\sqrt{n} + 2\sqrt{n/2} + 4\sqrt{n/4} +…$
Reduced it becomes $\sqrt{n} + \sqrt{2n} + \sqrt{4n} +…$
I'm pretty sure this summation happens log(n) times, which would make the equation be:
$$(2) \quad T(n)= \sum_{k=0}^{log(n)} \sqrt{2^kn}$$
Now I have no idea. I don't know how to solve a sum with log(n) bounds or if this is even set up right. How do I get from #2 to #1?
Best Answer
I don't think your solution to the recurrence is quite right, though it is close. But to answer your main question, note that you can write:
$$T(n)= \sum_{i=0}^{log(n)} \sqrt{2^i n} = \sqrt{n} \sum_{i=0}^{log(n)} \sqrt{2^i} = \sqrt{n} \sum_{i=0}^{log(n)} 2^{i/2}$$
Note that this is a variant of the well-known geometric series. You might not know its closed form, but we can derive it easily. We will derive a general result, as follows:
$$S = \sum_{i = 0}^{m - 1} a^{i/b}$$
That is:
$$S = a^{0/b} + a^{1/b} + \cdots + a^{(m - 1)/b}$$
Now what happens if we multiply through by $a^{1/b}$? We get:
$$a^{1/b} S = a^{0/b + 1/b} + a^{1/b + 1/b} + \cdots + a^{(m - 1)/b + 1/b}$$
That is:
$$a^{1/b} S = a^{1/b} + a^{2/b} + \cdots + a^{(m - 1)/b} + a^{m/b}$$
Note the RHS looks very similar to the original sum $S$, except it's missing the first term and has an extra last term. So, we account for them, and telescope:
$$a^{1/b} S + a^{0/b} - a^{m/b} = a^{0/b} + a^{1/b} + a^{2/b} + \cdots + a^{(m - 1)/b} = S$$
Solving for $S$, we get:
$$S = \sum_{i = 0}^{m - 1} a^{i/b} = \frac{a^{m/b} - a^{0/b}}{a^{1/b} - 1} = \frac{a^{m/b} - 1}{a^{1/b} - 1}$$
Plugging in $a = b = 2$ and $m = \log_2(n) + 1$ you get your result (this is where the $1 + \sqrt{2}$ factor comes from, for instance). Also, for the infinite sum variant, it's the exact same thing, except there is no need to account for $a^{m/b}$ since the sum is infinite, so, assuming it converges:
$$S = \sum_{i = 0}^{\infty} a^{i/b} = \frac{-1}{a^{1/b} - 1}$$
These are useful geometric sums to know about, or at least know how to derive!
(if you are not interested in the full derivation, then don't read beyond this point)
PS: you can use \tag{#} to tag equations, it's nicer than writing (#) at the beginning.
A general method for solving such recurrences is to find a pattern or "form" $F(i)$ such that if $T(n)$ can be interpreted as $F(i)$ then it can also be interpreted as $F(i + 1)$, where $F(i + 1)$ contains a "smaller" recurring term $T(n_i)$. You then calculate the maximum $i$ needed to make $T(n_i)$ constant, and let $i$ equal that value. That gives you a closed form for your recurrence. This is what you implicitly did, but you seem to have made some mistakes. A full derivation is given below.
Let's see what we get here. The first step is to find the pattern so substitute $T(n)$ into the recurrence a few times to see what's going on (not part of the proof, and note you've already done this):
$$T(n)= 2T(n/2) + \sqrt{n}$$
$$T(n)= 2\left ( 2 T(n/4) + \sqrt{n/2} \right ) + \sqrt{n} = 4 T(n / 4) + 2 \sqrt{n/2} + \sqrt{n}$$
$$T(n) = 4 \left ( 2T(n / 8) + \sqrt{n/4} \right ) + 2\sqrt{n/2} + \sqrt{n} = 8 T(n / 8) + 4\sqrt{n/4} + 2\sqrt{n/2} + \sqrt{n}$$
$$T(n) = 8 \left ( 2T(n / 16) + \sqrt{n/8} \right ) + 4\sqrt{n/4} + 2\sqrt{n/2} + \sqrt{n}\\ = 16 T(n / 16) + 8\sqrt{n/8} + 4\sqrt{n/4} + 2\sqrt{n/2} + \sqrt{n}$$
At this point the pattern is probably obvious. For all $i \geq 1$ we seem to be able to interpret $T(n)$ as:
$$T(n) = 2^i T(n / 2^i) + \sum_{k = 0}^{i - 1} 2^k \sqrt{n / 2^k} \tag{1}$$
And notice that as $i$ tends to infinity, $n / 2^i$ tends to zero, so this will yield a closed form for $T(n)$. Of course, we haven't proven anything yet. But we can show the above holds by induction. First, it holds for $i = 1$, where it just is your original recurrence. So, suppose that for some $i \geq 1$ we have:
$$T(n) = 2^i T(n / 2^i) + \sum_{k = 0}^{i - 1} 2^k \sqrt{n / 2^k}$$
Then, substituting in, we find:
$$T(n) = 2^i \left [ 2 T(n / 2^{i + 1}) + \sqrt{n / 2^i} \right ] + \sum_{k = 0}^{i - 1} 2^k \sqrt{n / 2^k}$$
Simplifying:
$$T(n) = 2 \cdot 2^i T(n / 2^{i + 1}) + 2^i \sqrt{n / 2^i} + \sum_{k = 0}^{i - 1} 2^k \sqrt{n / 2^k}$$
In other words:
$$T(n) = 2^{i + 1} T(n / 2^{i + 1}) + \sum_{k = 0}^{(i + 1) - 1} 2^k \sqrt{n / 2^k}$$
Bingo! By induction, we prove that $(1)$ is the general form of the recurrence. Now observe that the expression for some $i$ contains $T(n / 2^i)$. If we assume that $T(1) = c$ is a constant (by convention, we could assume that any $T(n)$ for $n \leq n_0$ is constant, that will just give us the same asymptotic complexity with a bigger hidden constant) then we solve:
$$n / 2^i = 1 ~ ~ \implies ~ ~ n = 2^i ~ ~ \implies ~ ~ i = \log_2(n)$$
And so when $i$ reaches $\log_2(n)$, the $T(n / 2^i)$ term goes constant (as you found). In other words:
$$T(n) = 2^{\log_2(n)} c + \sum_{k = 0}^{\log_2(n) - 1} 2^k \sqrt{n / 2^k} \tag{2}$$
Which is a closed form for your recurrence, albeit a messy one. The final step is to tidy up the closed form to make it easier to work with. First off note that we can simplify the $2^{\log_2(n)}$ term:
$$T(n) = cn + \sum_{k = 0}^{\log_2(n) - 1} 2^k \sqrt{n / 2^k}$$
Similarly, we note that the terms in the sum have $\sqrt{n}$ in common, let's pull it out and rewrite the summand to prepare it for a geometric series simplification (it should be obvious by now this is what is going to happen):
$$T(n) = cn + \sqrt{n} \sum_{k = 0}^{\log_2(n) - 1} 2^k \sqrt{1 / 2^k} = cn + \sqrt{n} \sum_{k = 0}^{\log_2(n) - 1} \sqrt{2^k} = cn + \sqrt{n} \sum_{k = 0}^{\log_2(n) - 1} 2^{k / 2}$$
Yup, that sum is now clearly some kind of geometric series, which can be evaluated analytically as:
$$\sum_{k = 0}^{m - 1} 2^{k / 2} = (1 + \sqrt{2})(2^{m/2} - 1)$$
(we proved this at the beginning of this answer)
Therefore - almost there - substituting $m = \log_2(n)$ we find that:
$$\sum_{k = 0}^{\log_2(n) - 1} 2^{k / 2} = (1 + \sqrt{2})(2^{\log_2(n)/2} - 1) = (1 + \sqrt{2})(\sqrt{n} - 1)$$
And finally we find (don't forget the multiplication by $\sqrt{n}$ outside the sum):
$$T(n) = cn + (1 + \sqrt{2})(n - \sqrt{n})$$
Which is the same as what WolframAlpha found, and for recurrences of the form $T(n) = aT(n/b) + f(n)$ you can kind of automate the above and find conditions of $a$, $b$ and the asymptotics of $f(n)$ which result in different types of asymptotic behaviour for $T(n)$ (aka the master theorem).
As you can see, none of the steps here were particularly involved:
the first step, finding the pattern, was pretty simple, as it involved expanding the recurrence and looking at the equations (usually for recurrences like this one you will find that the recurrence will progressively grow a "tail" which typically happens to be a geometric series).
the second step, proving that the pattern holds, was trivial (it usually is, since you are just formally proving that "the pattern obviously holds").
the third step, finding the limit on $i$ such that $T(n_i)$ goes constant is typically easy for most recurrences, and depends entirely on the term inside the recurring $T(\cdot)$ term: for $T(n / b)$ you will get $i = \log_b(n)$, for $T(n - 1)$ you will get $i = n$, for $T(\sqrt{n})$ you get $i = \log_2(\log_2(n))$, and so on.
the last step, simplifying the closed form by getting rid of the series or products you will probably have introduced, is by far the hardest of all, as if you don't end up with a nice and easy "pattern" in step 1 the recurrence may not be simplifiable. This might not be a problem in and of itself for asymptotics if you are able to bound it, though.
Also, it seems very long and tedious, but that is because I explained every step in great detail. You don't gain very much by using diagrams since as mentioned, you still need to do some analytic work at the end to simplify your series. I recommend you work through the above yourself to understand why and how this technique can be applied (it does not work easily for all recurrences, and should not be used without reservation because it can be quite long-winded in some cases where a simpler approach might work).
Try this one too for a challenge: $T(n) = \sqrt{n} T(\sqrt{n}) + n$