5
$\begingroup$

The book I am following explains the solution as,

As we can see,the size of sub problems at the first level of recursion is $n$.So, let us guess that $T(n)=O(n\log n)$ and try to prove that our guess is correct.

Doubt- Does initial problem size(i.e n) give a hint to reach $O(n\log n)$ ? How it does?

furthermore ,the book says

Let's start by trying to prove an upper bound $T(n)\le c\cdot n\log n$

\begin{align*} T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n \tag{1} \\ \le \sqrt{n}\cdot c\sqrt{n}\log(\sqrt{n}) + n \tag{2} \\ =n\cdot c\log (\sqrt{n})+ n \tag{3} \\ =n\cdot c\cdot\frac{1}{2}\log n+ n \tag{4} \\ \le c\cdot n\log n \tag{5} \end{align*} Last inequality assumes only that $$1\le c\cdot\frac{1}{2}\cdot \log n$$ This is correct if n is sufficiently large and for any constant c,no matter how small.So we are correct for upper bound.

I am not getting what's happening from $(1)$ to $(2)$ and that from $(4)$ to $(5)$. Also What does the last line prove ?

Improve this question
$\endgroup$
3
  • $\begingroup$ One question per question, please. You ask about 4 questions here, which is too many. The second part of your question seems to be purely mathematics and would be better asked on Math.SE. $\endgroup$
    – D.W. ♦
    Jul 11, 2016 at 18:13
  • $\begingroup$ Side note: the exact complexity of a process like $T(n) = n + \sqrt{n} T(\sqrt{n})$ solves to $T(n) \in \Theta(n \lg \lg n)$, so $O(n \lg n)$ isn't tight. (It's the natural guess if each level of recursion has the same total cost and you're square-rooting towards constant-size.) $\endgroup$
    – Craig Gidney
    Jul 12, 2016 at 0:05
  • $\begingroup$ Let me direct you towards our reference questions which cover some some techniques for such recurrences. $\endgroup$
    – Raphael ♦
    Jul 12, 2016 at 8:58

3 Answers 3

Reset to default
5
$\begingroup$

The book answer skips over some things. Here's a more detailed explanation.

You want to show $T(n)=O(n\log n)$, in other words there exists a $c>0$ such that $T(n)\le c\cdot n\log n$. [Actually, you need also to show that this inequality holds for all $n$ greater than some constant $N$, but we'll put this off temporarily.]

We'll use strong induction here; our induction hypothesis is that

$T(k)\le c\cdot k\log k$, for all $k<n$.

Now we'll expand the book's answer. $$\begin{align} T(n) &= \sqrt{n}\;T(\sqrt{n}) + n &\text{by definition} \\ &\le\sqrt{n}\;[c\cdot\sqrt{n}\log{\sqrt{n}}]+n &\text{by induction hypothesis, since $\sqrt{n}<n$}\\ &= cn(\log\sqrt{n})+n \end{align}$$ which answers your question about the step from $(1)\rightarrow(2)$. To get $(4) \rightarrow(5)$ the text wants to end up with $T(n)\le c\cdot n\log n$, so to conclude this they need $$ n\cdot c\cdot\frac{1}{2}\log n+n\le c\cdot n\log n $$ Dividing both sides of the desired equality by $n$ yields the needed condition: $$ \frac{c}{2}\log n+1\le c\log n $$ and this will be true when $1\le \frac{c}{2}\log n$. [The book actually doesn't need an unspecified $c$: in fact, $c=2$ will work perfectly here, since as long as $n\ge 2$ we'll have $1\le\log n$, satisfying our needed condition.]

In sum, we've shown by induction that the recurrence $T(n)= \sqrt{n}\log\sqrt{n}+n$ is satisfied by any function $T(n)=c\cdot n\log n$, as long as we pick a suitable $c$, which is exactly what was required.

It's worth pointing out that $O(n\log n)$ is an upper bound, but it's not the tightest upper bound possible. As gnasher729 pointed out, a better bound is $O(n\log\log n)$. It's a good exercise to do the same argument (with $c=1$) to show that $T(n)=n\log\log n$ is a solution to $T(n)=\sqrt{n}\;T(\sqrt{n})+n$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Got it..but what if I have to prove it for lower bound ? I would have to prove $T(n) \ge p\cdot n\log n $ and so as you suggested I should use induction $T(k)\ge p k\log k$ for all $k\gt n$ .....how do I proceed further? $\endgroup$
    – Aditya pratap singh
    Jul 12, 2016 at 8:14
  • $\begingroup$ @Adityapratapsingh. That'll be harder, since it's not true. You can, though, show that a solution is $T(n) = n\,\lg(\lg n)$, where $\lg n = \log_2n$. This means that your proposed $n\,\lg n$ is too large to be a lower bound. $\endgroup$
    – Rick Decker
    Jul 12, 2016 at 13:38
3
$\begingroup$

No. The problem size is defined to be $n$; that doesn't tell us anything about the solution to the recurrence.

See https://cs.stackexchange.com/a/2799/755 for details on how to use guess-and-check. How do you find a guess? Try a bunch of possibilities. Or, have an inspired guess. Or, graph the recurrence for $n=1$ to $n=100$ and use curve-fitting.

Improve this answer
$\endgroup$
3
$\begingroup$

The recursion formula obviously doesn't work for n = 1, since in that case it says that T (1) = 1 * T (1) + 1. So let's guess that T (2) = c, where c is unknown.

T (4) = 2 T (2) + 4 = 2c + 4.

T (16) = 4 T (4) + 16 = 8c + 32.

T (256) = 16 * T (16) + 256 = 128c + 16 * 32 + 256 = 128c + 16*16*3.

T (65536) = 256 T (16) + 65536 = 32768c + 256*256*3 + 256*256 = 32768c + 256*256*4.

It's time to guess that $T (2^k) = 2^{k-1}c + 2^k * log_2 (k)$.

Or $T (n) = cn/2 + n * log_2 (log_2 (n))$

Does this solve the recurrence relation? Assume that n is the square of an integer ≥ 2. Then according to the recurrence relation and the guess,

$T(n)= \sqrt{n}(c\sqrt{n}/2 + \sqrt{n} * log_2 (log_2 (\sqrt{n})))+n$

$T(n) = cn/2 + n * log_2 (log_2 (\sqrt{n}))+n$

$T(n) = cn/2 + n * log_2 (log_2 (n)/2)+n$

$T(n) = cn/2 + n * (log_2 (log_2 (n))-1)+n$

$T(n) = cn/2 + n * log_2 (log_2 (n)) - n + n = cn/2 + n * log_2 (log_2 (n))$

which is exactly what was proposed.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.