# Prove $T(n)=10T(\frac{n}{3})+n\sqrt{n}=\Theta(n^{\lg_3{10}})$ using induction

We have this recurrence: $$T(n)=10T(\frac{n}{3})+n\sqrt{n}.$$

We can solve it using Master Theorem and say it is $$\Theta(n^{\log_3{10}})$$. I want to prove it using induction but I don't know the correct and perfect procedure for proving these kinds of problems using induction.

I know that

• $$f(n) = \mathcal{O}(g(n))$$ if there exist positive constants $$c$$ and $$n_0$$ such that $$f(n)\le cg(n)$$ for all $$n\ge n_0$$.
• $$f(n) = \Omega(g(n))$$ if there exist positive constants $$c$$ and $$n_0$$ such that $$f(n) \geq cg(n)$$ for all $$n \ge n_0$$

And I know if $$f(n)=\mathcal{O}(g(n))$$ and $$f(n)=\Omega(g(n))$$, then $$f(n)=\Theta(g(n))$$. So I first tried to show $$T(n)=\mathcal{O}(n^{\log_3{10}})$$. I assumed we know $$T(n)\le cn^{\log_3{10}}$$ for some positive constant $$c$$.

Then we have:

\begin{align} T(n) = & 10T(\frac{n}{3})+n\sqrt{n}\\ \leq & 10(c(\frac{n}{3})^{\log_3{10}})+n\sqrt{n}\\ = & 10c(10)^{\log_3{\frac{n}{3}}}+n\sqrt{n}\\ = & 10c(10)^{(\log_3{n})-1}+n\sqrt{n}\\ = & c(10)^{\log_3{n}}+n\sqrt{n}\\ = & cn^{\log_3{10}}+n\sqrt{n} \end{align}

At this point I don't know how can I prove that this expression is lower than or equal to $$c_1n^{\log_3{10}}$$. I don't even know that $$c_1$$ is equal to the $$c$$ above necessarily or no? How can I complete this?

And we know this is the "step" part of the induction (if its correct), how can we prove the base cases and find $$n_0$$ and $$c$$.

• what does $\lg^{10}_3$ mean? Do you mean $\log_3(10)$? Commented Oct 23, 2023 at 3:10
• @whoisit Yes. Sorry for my fault. Commented Oct 23, 2023 at 4:10
• @PålGD Yes, it's obvious for me. But actually it's my first time proving these and I don't know how to continue the relations. Commented Oct 23, 2023 at 6:44
• – D.W.
Commented Oct 27, 2023 at 19:02

I'll solve a simpler recurrence, $$T(n) = 4T(n/2) + n,$$ but the point is the same, namely that your induction hypothesis is too weak.

We show something stronger: $$T(n) \leq c \cdot n^2 - dn$$ for some $$d$$. (!!)

So, by induction, we want to show that $$T(n) \leq cn^2 - dn$$, and we'll set $$d$$ at the end.

Induction hypothesis. For all $$m < n$$, $$T(m) \leq cm^2 - dm$$.

Induction step. $$T(n) = 4T(n/2) + n \leq 4(c \frac{n}{2}^2 - d\frac{n}{2}) + n = 4(c\frac{n^2}{4} - d\frac{n}{2}) + n$$.

Simplify to get $$cn^2 - 2dn + n = cn^2 -dn -dn +n = cn^2 -dn + (1-d)n$$.

Now we've got it: $$cn^2 -dn + (1-d)n \leq cn^2 -dn$$ as long as $$d \geq 1$$.

Let $$d = 1$$, and we have that $$T(n) \leq cn^2 -dn$$, which is what we set out to prove. It follows that $$T(n) = O(n^2)$$.

For your problem, first try to solve the above, then solve $$T(n) = 4T(n/2) + n \sqrt n$$. For the latter, you will probably need to show that $$T(n) \leq cn^2 - dn \sqrt n$$, and it should probably work if you just set $$d = \sqrt 2 + 1$$.

• To prove $T(n)=4T(\dfrac{n}{2})+n\sqrt{n}=\mathcal{O}(n^2)$ if we assume $T(n)\leq cn^2-dn\sqrt{n}$, I tried this: \begin{align} T(n) &=4T(\dfrac{n}{2})+n\sqrt{n}\\ &\leq 4\left[c(\frac{n}{2})^2-d(\frac{n}{2})^{\frac{3}{2}}\right]+n\sqrt{n}\\ &= cn^2-d\sqrt{2}n\sqrt{n}+n\sqrt{n}\\ &=cn^2-dn\sqrt{n}-(\sqrt2-1)dn\sqrt{n}+n\sqrt{n}\\ &=cn^2-dn\sqrt{n}-n\sqrt{n}\left[(\sqrt2-1)d-1\right] \end{align} That would be lower than or equal to $cn^2-dn\sqrt{n}$ if $d>\sqrt2+1$. Am I right? In this form, shouldn't we find $n_0$ and $c$? Commented Oct 24, 2023 at 20:02
• You are right that $d \geq \sqrt 2 + 1$. You don't have to say anything about $n_0$, but you need to notice that $c \geq d+1$, (provided $T(1) = 1$), otherwise the BC doesn't go through. Commented Oct 25, 2023 at 9:23
Let $$n = 3^m$$ and Q(m) = T($$3^m$$), and rewrite the recursion in terms of m and it’s easy.
• I tried. We will have $Q(m)=10Q(m-1)+3^{\frac{3m}{2}}$ and we should prove $Q(m)=\mathcal{O}(10^m)$. But I reach $Q(m)\leq c\times 10^m + 3^{\frac{3m}{2}}$ that is not lower or equal to $c\times 10^m$ for any $c$ and $m$. What should I do? Any help is appreciated! Commented Oct 24, 2023 at 6:35