# For $T(n) = 16(T/4) + n^2\lg^3n$ prove: $T(n) = \Theta(n^2\lg^3n)$

Define: $$\lg x = \log_2x$$.

Let $$f(n), g(n)$$ be some non-negative functions.

Define $$f(n) = \Theta (g(n))$$ if $$\exists c_1,c_2 \in R\colon 0 < c_1g(n) \leq f(n) \leq c_2g(n)$$

I want to prove that the function defined by the recurrence relation $$T(n) = 16(T/4) + n^2\lg^3n$$ has the asymptotics $$T(n) = \Theta(n^2\lg^3n)$$

I wanted to prove that by substitution method:

$$T(n/4) \leq n^2\lg^3n$$

Now,

$$T(n) \leq 16(n^2\lg^3n) + n^2\lg^3n = 17n^2\lg^3n$$

But in order for the proof to work, I should have gotten

$$T(n) \leq n^2\lg^3n$$

I also need to show that this is a lower bound, but I want to start by showing that it's an upper bound.

What is the right way to prove these things?

• You are actually trying a proof by induction, not by substitution. – Yuval Filmus Apr 5 '20 at 17:07
• Your calculation is incorrect, but if you fix it it still shows you have a problem. – gnasher729 Apr 5 '20 at 17:46

$$T(n) = 16 T(n/4) + n^2\log^3 n$$ has solution $$T(n) = \Theta(n^2 \log^4 n)$$.
To see this notice that this recurrence fits in the general form $$T(n) = a T(n/b) + f(n)$$ once you set $$a=16, b=4, f(n)=n^2\log^3 n$$.
Since $$f(n) = n^2 \log^3 n = \Theta( n^{ \log_b a } \cdot \log^k n)$$ for $$k=3$$, you can apply the Master theorem to conclude that $$T(n) = \Theta(n^{ \log_b a } \cdot \log^{k+1} n)$$.