# Solving a recurrence relation with √n as parameter

Consider the recurrence

$\qquad\displaystyle T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + c\,n$

for $n \gt 2$ with some positive constant $c$, and $T(2) = 1$.

I know the Master theorem for solving recurrences, but I'm not sure as to how we could solve this relation using it. How do you approach the square root parameter?

-

## migrated from stackoverflow.comOct 31 '12 at 22:42

This question came from our site for professional and enthusiast programmers.

The Master theorem is not applicable here; $\sqrt{n}$ can not be written as $\frac{n}{b}$. What else have you tried? – Raphael Oct 31 '12 at 23:18
@Raphael : I tried the substiution method, but seemed to get stuck on what value I should choose to substitute. – KodeSeeker Oct 31 '12 at 23:27
How about "unfold the recurrence a few times, observe a pattern, guess the solution and prove it"? – Raphael Oct 31 '12 at 23:40
Well this is a first ive come across of this type, maybe some help here would help me work out future problems of the nature with ease. – KodeSeeker Nov 1 '12 at 0:08
Since you mention Master Theorem, I assume you need to solve this relation for asymptotic bounds, and don't really need the closed form expression. Given below, there are some good solutions to find the closed form expression, which also give the asymptotic complexity. However, if you only need the asymptotic complexity, the analysis is simpler. Have a look here for a good explanation on finding asymptotic complexities, with a nice intuitive solution for your problem instance. – Paresh Nov 3 '12 at 13:33

We will use Raphael's suggestion and unfold the recurrence. In the following, all logarithms are base 2. We get

\begin{align*} T(n) &= n^{1/2} T(n^{1/2}) + cn \\ &= n^{3/4} T(n^{1/4}) + n^{1/2} c n^{1/2} + cn\\ &= n^{7/8} T(n^{1/8}) + n^{3/4} c n^{1/4} + 2cn\\ &= n^{15/16} T(n^{1/16}) + n^{7/8} c n^{1/8} + 3cn \\ & \ldots \\ &= \frac{n}{2} T(2) + c n \beta(n) \end{align*}. where $\beta(n)$ is how many times you have to take the square root to start with n, and reach 2. It turns out that $\beta(n) = \log \log n$. How can you see that? Consider: \begin{align*} n &= 2^{\log n}\\ n^{1/2} &= 2^{\frac{1}{2} \log n} \\ n^{1/4} &= 2^{\frac{1}{4} \log n} \\ \ldots \end{align*} So the number of times you need to take the square root in order to reach 2 is the solution to $\frac{1}{2^t} \log n \approx 1$, which is $\log \log n$. So the solution to the recursion is $c n \log \log n + \frac{1}{2}n$. To make this absolutely rigorous, we should use the substitution method and be very careful about how things get rounded off. When I have time, I will try to add this calculation to my answer.

-
"You have to take the square root $\log\log n$ times" -- is that something a beginner can be expected to see? Also, your result does not fit Yuval's; is it intended to by asymptotically only? – Raphael Nov 1 '12 at 14:12
@Raphael: Yuval made an error, which he's now corrected. I'll explain the square root in my answer. – Peter Shor Nov 1 '12 at 14:44
Another idea to see that the recursion takes $O(\log\log n)$ is the following: By taking the square root of $n$ you halve the digits needed for the binary representation of $n$. So your input needs $w=\log n$ bits and you divide the word-size by 2 for every level of the recursion. Hence you stop after $\log w=\log\log n$ steps. – A.Schulz Nov 1 '12 at 17:59

If you write $m=\log n \space$ you have $T(m) = {m \over 2}\cdot T({m\over 2}) + c\cdot 2^m\space$.

Now you know the recursion tree has hight of order $O(\log m)$, and again it's not hard to see it's $O(2^m)\space$ in each level, so total running time is in: $O((\log m) \cdot 2^m)\space$, which concludes $O(n \cdot \log \log n)\space$ for $n$.

In all when you see $\sqrt n$ or $n^{a \over b}, a<b \space$, is good to check logarithm.

P.S: Sure proof should include more details by I skipped them.

-

In your comment you mentioned that you tried substitution but got stuck. Here's a derivation that works. The motivation is that we'd like to get rid of the $\sqrt{n}$ multiplier on the right hand side, leaving us with something that looks like $U(n) = U(\sqrt{n}) + something$. In this case, things work out very nicely:

\begin{align} T(n) &= \sqrt{n}\ T(\sqrt{n}) + n & \text{so, dividing by n we get}\\ \frac{T(n)}{n} &= \frac{T(\sqrt{n})}{\sqrt{n}} + 1 &\text{and letting n = 2^m we have}\\ \frac{T(2^m)}{2^m} &= \frac{T(2^{m/2})}{2^{m/2}} + 1 \end{align} Now let's simplify things even further, by changing to logs (since $\lg \sqrt{n} = (1/2)\lg{n}$). Let \begin{align} S(m) &= \frac{T(2^m)}{2^m} & \text{so our original recurrence becomes}\\ S(m) &= S(m/2)+1 \end{align} Aha! This is a well-known recurrence with solution $$S(m)=\Theta(\lg m)$$ Returning to $T(\,)$, we then have, with $n=2^m$ (and so $m=\lg n$), $$\frac{T(n)}{n} = \Theta(\lg\,\lg n)$$ So $T(n) =\Theta(n\,\lg\,\lg n)$.

-

Let's follow Raphael's suggestion, for $n = 2^{2^k}$: \begin{align*} T(n) = T(2^{2^k}) &= 2^{2^{k-1}} T(2^{2^{k-1}}) + c2^{2^k} \\ &= 2^{2^{k-1}+2^{k-2}} T(2^{2^{k-2}}) + c(2^{2^k} + 2^{2^k}) \\ &= \cdots \\ &= 2^{2^{k-1}+2^{k-2}+\cdots+2^0} T(2^{2^0}) + c(2^{2^k} + 2^{2^k} + \cdots + 2^{2^k}) \\ &= 2^{2^k-1} + ck2^{2^k} \\ &= (c\log\log n + 1/2)n. \end{align*}

Edit: Thanks Peter Shor for the correction!

-
How did you come up with $2^{2^k}$? Note for OP: "$\dots$" is not a proof, you'll have to provide that still (usually by induction). – Raphael Nov 1 '12 at 14:11
@Raphael: It's nearly a proof. You just need to show that it's also correct for numbers not of the form $2^{2^k}$. – Peter Shor Nov 1 '12 at 14:59
Actually, the recurrence is only well-defined for numbers of the form $2^{2^k}$, since otherwise, at some point $\sqrt{n}$ wouldn't be an integer, and you'll never reach the base case $T(2)$. – Yuval Filmus Nov 1 '12 at 18:18
If this recurrence actually came from an algorithm, it would probably really be something more like $T(n) = \lceil \sqrt{n} \rceil T(\lceil \sqrt{n} \rceil) + cn$. – Peter Shor Nov 1 '12 at 18:35

You should try to make an educated guess about the form of the function that will help you getting a step forward.

For example you need to notice first if you can substitute $T(n)=S(n) +d$ or $T(n)=dS(n)$ and still get the equation valid for any constant d. This is not the case so we go on.

It is kind of obvious that if you take $T(n)=nS(n)$ you can safely get rid of $n$

$$nS(n)=\sqrt{n}\sqrt{n}S(\sqrt{n})+cn=nS(\sqrt{n})+cn$$ $$S(n)=S(\sqrt{n})+c$$

Now any $S(n)=P(n)+d$ will do so linear part is free to choose and we keep on. Second, we can fix c to whatever we like since we can divide through c and get the valid equation. But which c to fix? We suspect $P(n)=\log(Q(n))$ and if we plug in we have

$$P(n)=P(\sqrt{n})+c$$ $$\log(Q(n))=\log(Q(\sqrt{n}))+c$$

For this reason we will plug in $c=log(2)$, since this is what makes the equation nice, (remember the location of this $P(n)=P(\sqrt{n})+c$, $\frac{P(n)\log(2)}{c} =\frac{P(\sqrt{n})\log(2)}{c}+\log(2)$, $P'(n)=\frac{P(n)\log(2)}{c}$,

$$P'(n)=\log(Q(n))$$ $$\log(Q(n))=\log(Q(\sqrt{n}))+log(2)=\log(2Q(\sqrt{n}))$$ $$Q(n)=2Q(\sqrt{n})$$

Quite obviously we have $Q(n)=\log(n)$ as a solution.

Step by step back:

$T(n)=n(d+c\frac{log(log(n))}{log(2)})$

If you plug in back you have

$$n(d+c\frac{log(log(n))}{log(2)})=\sqrt{n}\sqrt{n}(d+c\frac{log(log(\sqrt{n})}{log(2)})+cn$$

$$d+c\frac{log(log(n))}{log(2)}=d+c\frac{log(log(\sqrt{n}))}{log(2)}+c$$ $$\frac{log(log(n))}{log(2)}=\frac{log(log(\sqrt{n}))}{log(2)}+1$$ $$log(log(n))=log(log(\sqrt{n}))+log(2)$$ $$log(log(n))=log(2log(\sqrt{n}))$$

$$log(n)=2\frac{1}{2}log(n)$$

It looks like we need more than $T(1)=2$ since we have only the connection between c and d with $T(1)=2$

Assuming d = 0 we have $c=\frac{\log(2)}{2\log(\log(2))}$.

-

O(n log log n ) is the order of given question using back substitution .

-
Could you rewrite your picture to MathJax? We discourage images with text as the answers. – EvilJS Jan 26 at 18:47