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


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

  • $\begingroup$ You are actually trying a proof by induction, not by substitution. $\endgroup$ Apr 5, 2020 at 17:07
  • $\begingroup$ Your calculation is incorrect, but if you fix it it still shows you have a problem. $\endgroup$
    – gnasher729
    Apr 5, 2020 at 17:46

1 Answer 1


What you want to prove is false.

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


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.