1
$\begingroup$

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$.

$\endgroup$
4

2 Answers 2

1
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ 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$? $\endgroup$ Oct 24, 2023 at 20:02
  • $\begingroup$ 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. $\endgroup$
    – Pål GD
    Oct 25, 2023 at 9:23
  • $\begingroup$ Can you tell me what to do about this one, please? $\endgroup$ Oct 26, 2023 at 13:45
0
$\begingroup$

Let $n = 3^m$ and Q(m) = T($3^m$), and rewrite the recursion in terms of m and it’s easy.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ Oct 24, 2023 at 6:35

Your Answer

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

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