0
$\begingroup$

I'm confused on how to prove the below using induction:

T(n) = 3T(n/9) + √n

I have been given the base case T(1) = 1. I know using the master theorem that the time complexity is O(√n log n). However, when trying to find the inductive hypothesis (function form) of the recurrence by substituting k = 0, 1, 2, 3... into T(9^k), I'm not sure how to find the function form.

Thanks!

$\endgroup$

2 Answers 2

0
$\begingroup$

$$\begin{align}T(9^4)&=3T(9^3)+3^4 \\&=3(3T(9^2)+3^3)+3^4=3^2T(9^2)+2\cdot3^4 \\&=3^2(3T(9)+3^2)+2\cdot3^4=3^3T(9)+3\cdot3^4 \\&=3^3(3T(1)+3^1)+3\cdot3^4=3^4T(1)+4\cdot3^4 \end{align}$$

and we can infer

$$T(9^m)=3^m(T(1)+m),$$ which is

$$T(n)=\sqrt n(T(1)+\log_9(n)).$$


Verification:

$$\begin{align}\sqrt n(T(1)+\log_9(n))&=3\sqrt{\frac n9}\left(T(1)+\log_9\left(\frac n9\right)\right)+\sqrt n \\&=\sqrt n(T(1)+\log_9(n))-\sqrt n+\sqrt n\end{align}$$

is indeed an identity.

$\endgroup$
0
$\begingroup$

Other method:

We divide both membres by $\sqrt n$:

$$\frac{T(n)}{\sqrt n}=\frac{3T\left(\dfrac n9\right)}{\sqrt n}+1=\frac{T\left(\dfrac n9\right)}{\sqrt{\dfrac n9}}+1.$$

This is of the form

$$S(n)=S\left(\frac n9\right)+1$$ and denotes the number of times you can divide by $9$ before reaching $1$, or $$\log_9(n)+S(1).$$

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