Show that $T(n)$ is bounded both above and below by $n$ (abusing the Big O notation) for some positive constants $c_1$ and $c_2$:

$$ T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n) $$

Let's do some substutution for proving first that is $O(n)$. Because $T\left(\frac n3\right) \le c\frac n3$:

$$ \begin{align} T(n) &= 3T\left(\frac n3\right) + \sqrt n = 3c\frac n3 + \sqrt n\\ &= cn + \sqrt n \le cn \end{align} $$

So $cn + \sqrt n \le cn$: where we are adding $\sqrt n$ on the left and pretending that we get something bigger on the right. I would say that $T(n) = \Omega(n)$ for $c \ge 1$, but not $T(n) = O(n)$!

I'm sure that I'm wrong (I have the solution sheet), can you help me find out why?

EDIT: actually I've found a lot of examples where induction does not work, like:

$$ T(n) = 2T\left(\frac n2\right) +1 $$

The technique to solve this (subtract a lower order term from the right side of the inequality we wish to prove) is explained by Hagen von Eitzen answer. The question remains: why does induction not work in this case?

  • 1
    $\begingroup$ To reinforce Aryabhata's answer via comment: you started with $T(n/3) \leq cn/3$, but then 'clarified' that to $T(n/3) = cn/3$ ; but the former doesn't imply the latter at all. $\endgroup$ – Steven Stadnicki Apr 6 '13 at 17:42

You are given $T(n) = 3 T(n/3) + \sqrt{n}$ and want to prove that $T(n) = O(n)$.

Your induction assumption: there is some $c$ such that $T(k) \le ck$ for all $k < n$. Fine so far.

Now you are trying to use the recurrence:

$T(n) = 3 T(n/3) + \sqrt{n} \le cn + \sqrt{n}$

Thus if, $T(n/3) \le cn/3$ then $T(n) \le cn + \sqrt{n}$

Note that this only shows an upper bound on $T(n)$, given the upper bound on $T(n/3)$.

This does not contradict the fact that $T(n) \le cn$

This only means that the upper bound assumption you started with: $T(n/3) \le cn/3$, though true, was not sufficient for your purposes and you need to pick a stronger hypothesis.

(One explanation this happens is that not all functions in $O(n)$ satisfy $T(n) \le 3T(n/3) + \sqrt{n}$. The induction proof you are trying to apply applies to all functions in $O(n)$)

That is one reason you need to consider the lower order terms.

For instance, if you assume that $T(k) \le ck - 2\sqrt{k}$, then I believe the induction proof goes through.

| cite | improve this answer | |

Show that $T(n) = O(n-\sqrt n)$ and then use $n-\sqrt n=O(n)$:

If $T(\frac n3)<c\left(\frac n3-\sqrt{\frac n3}\right)$ then $$\begin{align} T(n)&= 3T(\frac n3)+\sqrt n\\&< cn-c\sqrt 3\sqrt n+\sqrt n \\&= cn - (c\sqrt 3-1)\sqrt n\\ &\le c(n-\sqrt n)\end{align}$$ provided $c\sqrt 3-1\ge c$, i.e. $c\ge \frac1{\sqrt 3-1}$.

| cite | improve this answer | |
  • $\begingroup$ Thanks for explaining you technique, but I'd like to understand what I'm doing wrong in the question... $\endgroup$ – Polmonino Apr 6 '13 at 16:59
  • $\begingroup$ Sometimes the obvious approach does not work. The problem is that $\max_{k\le n}\frac{T(k)}{k}$ may be strictly increasing,thus you will never be able to use a $c$ barely working for $\frac n3$ to also work for $n$. By the way note that $O(n-\sqrt n)\equiv O(n)$, so in a way the induction worked like charm, it was just that $n$ was a bad representative of this $O$ class to begin with. $\endgroup$ – Hagen von Eitzen Apr 6 '13 at 17:21

You're correct to be skeptical about the substitution you've employed - because you started with a presumed constant $c$ for your equation $T(n)\in O(n) \implies T(n)\leq cn$ and then showed that the fact that that constant worked for $\frac{n}{3}$ doesn't imply that the same constant works for $n$. But that doesn't mean that it's impossible that any constant works; it just means that a finer analysis is required.

Instead, for a problem like this it's better to substitute $n=3^t$ and recast $T(n) = T(3^t) = U(t)$; then the equation becomes $U(t) = 3U(t-1) + 3^{t/2}$. From here, we can expand recursively: $$\begin{array} \\ U(t) &= 3\left(3U(t-2)+3^{(t-1)/2}\right)+3^{t/2} \\ &= 3^2 U(t-2) + 3^{(t+1)/2} + 3^{t/2} \\ &= 3^2\left(3U(t-3)+3^{(t-2)/2}\right) + 3^{(t+1)/2} + 3^{t/2} \\ &= 3^3U(t-3) + 3^{(t+2)/2}+3^{(t+1)/2}+3^{t/2} \\ &\ldots \\ &= 3^tU(0) + \sum_{i=t}^{2t-1}3^{i/2} = 3^tU(0) + 3^{t/2}\sum_{i=0}^{t-1} 3^{i/2} \end{array}$$ Now,from here you should be able to sum the geometric series and find a value for $U(t)$; once you have that, you can plug back in $3^t=n$ and find an inequality for $T(n)$.

| cite | improve this answer | |
  • $\begingroup$ Please, take a look at my edits. I'd like understand why induction does not work in this particular case. I'll lear other techniques (like master theorem) but - for now - I'm interested in substitution. $\endgroup$ – Polmonino Apr 6 '13 at 17:12

Suppose the base three representation of $n$ is given by $$ n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 3^k$$ and we let the base case be $T(0) = 0.$ Then it is not difficult to see that $$ T(n) = \sum_{j=0}^{\lfloor \log_3 n \rfloor} 3^j \sqrt{\sum_{k=j}^{\lfloor \log_3 n \rfloor} d_k 3^{k-j}}.$$

Now to get an upper bound on this consider the case of all digits being two, giving $$ T(n)\le \sum_{j=0}^{\lfloor \log_3 n \rfloor} 3^j \sqrt{\sum_{k=j}^{\lfloor \log_3 n \rfloor} 2\times 3^{k-j}} = \sum_{j=0}^{\lfloor \log_3 n \rfloor} 3^j \sqrt{3^{\lfloor \log_3 n \rfloor -j+1}-1} \\ \le \sqrt{3}^{\lfloor \log_3 n \rfloor+1} \sum_{j=0}^{\lfloor \log_3 n \rfloor} 3^j \sqrt{3}^{-j} = \sqrt{3}^{\lfloor \log_3 n \rfloor+1} \sum_{j=0}^{\lfloor \log_3 n \rfloor}\sqrt{3}^j = \sqrt{3}^{\lfloor \log_3 n \rfloor+1} \frac{\sqrt{3}^{\lfloor \log_3 n \rfloor+1}-1}{\sqrt{3}-1}.$$

For a lower bound consider the case of all digits being zero except the first one, giving $$ T(n)\ge \sum_{j=0}^{\lfloor \log_3 n \rfloor} 3^j \sqrt{3}^{\lfloor \log_3 n \rfloor-j} = \sqrt{3}^{\lfloor \log_3 n \rfloor} \sum_{j=0}^{\lfloor \log_3 n \rfloor} 3^j \sqrt{3}^{-j} = \sqrt{3}^{\lfloor \log_3 n \rfloor} \sum_{j=0}^{\lfloor \log_3 n \rfloor} \sqrt{3}^j \\= \sqrt{3}^{\lfloor \log_3 n \rfloor} \frac{\sqrt{3}^{\lfloor \log_3 n \rfloor+1}-1}{\sqrt{3}-1}$$

Finally, taking the leading terms of the upper and the lower bound together, we have shown that $$ T(n) \in \Theta\left(\sqrt{3}^{\lfloor \log_3 n \rfloor} \times \sqrt{3}^{\lfloor \log_3 n \rfloor}\right) = \Theta\left(3^{\lfloor \log_3 n \rfloor} \right) = \Theta(n).$$

The next term in the asymptotic expansion is $\sqrt{3}^{\lfloor \log_3 n \rfloor}\sim\sqrt{n}.$

A better upper bound can be found by using the asymptotic expansion of $\sqrt{1-x}$ in a neighborhood of zero, using $$ \sqrt{3^{\lfloor \log_3 n \rfloor -j+1}-1} \\= \sqrt{3^{\lfloor \log_3 n \rfloor -j+1}} \left(1 - \frac{1}{2} \left(\frac{1}{3^{\lfloor \log_3 n \rfloor -j+1}}\right) - \frac{1}{8} \left(\frac{1}{3^{\lfloor \log_3 n \rfloor -j+1}}\right)^2 - \frac{1}{16} \left(\frac{1}{3^{\lfloor \log_3 n \rfloor -j+1}}\right)^3 - \cdots\right).$$

| cite | improve this answer | |
  • $\begingroup$ There is more material on this method here. $\endgroup$ – Marko Riedel Apr 6 '13 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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