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

In summary: Thinking)No, you don't have to find $g(n)$--you can just use the substitution method to find the pattern that holds for all $n$, and then use induction to prove that the function $T(n)$ is asymptotically bounded.
  • #1
evinda
Gold Member
MHB
3,836
0
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? :confused:
 
Physics news on Phys.org
  • #2
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$$
 
Last edited:
  • #3
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)
 
  • #4
evinda said:
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.​
 
  • #5
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)
 
  • #6
evinda said:
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.
 
  • #7
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)
 

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

1. What is an upper bound for a recurrence relation?

An upper bound for a recurrence relation is the maximum possible value that the recurrence relation can reach. It is used to determine the worst-case scenario for the algorithm or process described by the recurrence relation.

2. What is the significance of the upper bound in a recurrence relation?

The upper bound in a recurrence relation is significant because it helps us understand the time complexity of the algorithm or process. It allows us to determine the efficiency of the algorithm and make comparisons with other algorithms.

3. How is the upper bound calculated for a recurrence relation?

The upper bound for a recurrence relation is typically calculated by analyzing the algorithm and determining the maximum number of operations it can perform in the worst-case scenario. This is often done by using techniques such as substitution, iteration, or the Master Theorem.

4. What does the notation "T(n) <= c n^2 log^2 n" mean?

This notation represents the upper bound for the recurrence relation, where T(n) represents the time complexity of the algorithm or process, n represents the input size, and c is a constant. The log^2 n term indicates that the time complexity grows logarithmically with the input size.

5. How does the upper bound impact the efficiency of an algorithm?

The upper bound directly impacts the efficiency of an algorithm, as it determines the maximum amount of time the algorithm can take to complete. A lower upper bound indicates a more efficient algorithm, while a higher upper bound suggests a less efficient algorithm.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
0
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
855
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
1K
Replies
0
Views
554
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
798
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
760
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
Back
Top