Upper Bound for Recurrence Relation: $T(n) \leq c n^2 \log^2 n$

[evinda]

Hello! (Wave)

I want to find an asymptotic upper bound for the recurrence relation: $T(n)=9T \left (\frac{n}{3} \right ) + n^2 \log n $, $T(n)=c, \text{ when } n \leq 9$, using the following method:

We choose a specific function $f(n)$ and we try to show that for an appropriate $c>0$ and an appropriate $n_0 \in \mathbb{N}$, it stands that $T(n) \leq c f(n)$.
We suppose that $T(k) \leq c f(k), \forall k<n$ and we try to show that it stands for $n$.

Could we do it like that? (Thinking)

$T(n)=9T \left (\frac{n}{3} \right ) + n^2 \log n= \\

9 \cdot ( 9T \left ( \frac{n}{3^2} \right ) + \frac{n^2}{3^2} \log \left ( \frac{n}{3}\right)) +n^2 \log n =

\\ 9^2 T \left ( \frac{n}{3^2} \right )+ 9 \frac{n^2}{3^2} \log \left ( \frac{n}{3}\right) +n^2 \log n=

\\ = \dots =\\

9^i T\left ( \frac{n}{3^i} \right )+ \sum_{j=0}^{i-1} n^2 \log {\frac{n}{3^j}}=\\

9^i T\left ( \frac{n}{3^i} \right )+ n^2 \sum_{j=0}^{i-1} (\log n- j\log 3)= \\

9^i T\left ( \frac{n}{3^i} \right )+ n^2 \log n \sum_{j=0}^{i-1} 1 - \log 3 n^2 \sum_{j=0}^{i-1} j = \\

9^i T\left ( \frac{n}{3^i} \right )+ n^2 \ \log n \ i - \log 3 \ n^2 \ \frac{i(i-1)}{2} $For $i=\log_3 n $:

$T(n)=cn^2+n^2 \ \log n \ \log_3 n-\log 3 \ n^2 \frac{1}{2} (\log_3^2 n-\log_3n) \leq K n^2 \log^2n=O(n^2 \log^2n)$We will show that $T(n)=O(n^2 \log^2n)$.

We suppose that $\exists c>0$ such that $\forall k <n$ $T(k) \leq c k^2 \log^2k$.

$T(n)=9T \left (\frac{n}{3} \right ) + n^2 \log n \leq c n^2 \log^2 \left ( \frac{n}{3} \right ) + n^2 \log n=c n^2 \log^2n -\log^2 3 + n^2 \log n$

Is it right so far? Or have I done something wrong? (Thinking)

Is the substitution method a good way to find a function, in order to apply the method I am asked to use?

 

[Nono713]

Technically you should set $i = \log_3(n / 9)$ or something like that because $T(n)$ turns constant for $n < 9$, not $n < 1$. But yes, that is essentially correct, and is a good way of solving recurrences: exploiting a pattern in the recurrence to set up an inductive argument that says "if $T(n)$ looks like this after iterating $i$ times, then it still looks like this after iterating $i + 1$ times" and then plug in the number of times it should iterate to obtain a closed form. In this case the general form of the recurrence, as you appear to have discovered, was:
$$T(n) = 9^i T \left ( \frac{n}{3^i} \right ) + \sum_{k = 0}^{i - 1} n^2 \log \left ( \frac{n}{3^k} \right )$$
Which gives you something along the lines of $T(n) = c_1 n^2 + c_2 n^2 \log^2{n}$ for constants $c_1, c_2$ depending on what you plug into $i$, and then finding an upper bound based on that closed form of the recurrence is perfectly valid. And indeed $T(n) \in O(n^2 \log^2{n})$.

PS: if you would like to practice solving recurrences, here is a tricky one that you can work on - but please make a new thread for it if you need help - find a closed form for the recurrence below and tight upper/lower bounds:
$$T(n) = \sqrt{n} T(\sqrt{n}) + n$$
​

 

[evinda]

So, is the substitution method a right way to find a hypothesis of the solution of the recurrence relation, in order to use the method I am asked to use (Strong Induction), or is there a better way? (Thinking)

 

[Nono713]

So, is the substitution method a right way to find a hypothesis of the solution of the recurrence relation, in order to use the method I am asked to use (Strong Induction), or is there a better way? (Thinking)

Yes, it is "right" in the sense of being correct mathematically, and it is reasonably easy in this case (for other recurrences there may be better ways of doing it). Though I wouldn't call your solution rigorous: you used substitution to find the pattern, but you did not prove that the pattern holds no matter how many times you substitute $T(n)$. Just iterating it a couple times isn't a proof! In other words, you need to show that for all $i$:
$$T(n) = 9^i T \left ( \frac{n}{3^i} \right ) + \sum_{k = 0}^{i - 1} n^2 \log \left ( \frac{n}{3^k} \right )$$
Implies:
$$T(n) = 9^{i + 1} T \left ( \frac{n}{3^{i + 1}} \right ) + \sum_{k = 0}^i n^2 \log \left ( \frac{n}{3^k} \right )$$
That is your inductive step to solve the recurrence by (strong) induction. Setting $i = \log_3(n)$ is only the final step of the process.​

 

[evinda]

I want to prove by induction, that $T(n)=O(g(n)) \Rightarrow T(n) \leq c g(n)$.

Don't I have to find from the substitution method only the function $g(n)$ ? Or am I wrong? (Thinking)

 

[Nono713]

I want to prove by induction, that $T(n)=O(g(n)) \Rightarrow T(n) \leq c g(n)$.

Don't I have to find from the substitution method only the function $g(n)$ ? Or am I wrong? (Thinking)

I don't know, I don't have your lecture notes with me. You have found a closed form for $T(n)$ and upper-bounded it as per the problem statement. That seems perfectly fine to me. The upper-bounding step in and of itself is comparatively easy, so I'm not sure what you mean.

 

[evinda]

I am supposed to use this method:

We choose a specific function $f(n)$ and we try to show that for an appropriate $c>0$ and an appropriate $n_0 \in \mathbb{N}$, it stands that $T(n) \leq c f(n)$.
We suppose that $T(k) \leq c f(k), \forall k<n$ and we try to show that it stands for $n$.With the substitution method, I only wanted to find the specific function $f(n)$, in order to apply the above method. Am I wrong? (Thinking)