1
$\begingroup$

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?

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

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.