I can not find the appropriate variable to change the second part $n^2\mathrm{log}^2n$.

up vote 1 down vote accepted

$T(n)= a T(n/b)+ f(n) $

  • A generalization that usually works; set $n= b^k$.

With backward substitution method.

$T(n)=4T(n/2)+n^2 log^2 n $

  • take $n = 2^k$

\begin{align} T(2^k) & = 4 T(2^{k-1}) + 2^{k} \log^2 2^k \\ & = 4 T(2^{k-1}) + 2^{2k} k^2 \\ table (& \\ T(n^{k-1}) & = 4 T(2^{2}) + 2^{2(k-1)} (k-1)^2 \\ T(n^{k-2}) & = 4 T(2^{3}) + 2^{2(k-2)} (k-2)^2 \\ T(n^{k-3}) & = 4 T(2^{4}) + 2^{2(k-3)} (k-3)^2 \\ ) & \\ T(2^k) & = 4 [4 T(2^{k-2}) + 2^{2(k-1)} (k-1)^2 ] + 2^{2k} k^2 \\ & = 4^2 T(2^{k-2}) + 2^{2k} (k-1)^2 + 2^{2k} k^2 \\ & = 4^2 [ 4 T(2^{k-3}) + 2^{2(k-2)} (k-2)^2] + (2^{2k} (k-1)^2 + 2^{2k} k^2) \\ & = 4^3 T(2^{k-3}) + (2^{2k} (k-2)^2 + 2^{2k} (k-1)^2 + 2^{2k}k^2) \\ & = 4^3 [4 T(2^{k-4}) + 2^{2(k-3)} (k-3)^2] + (2^{k} (k-2)^2 + 2^{k} (k-1)^2 + 2^{k}k^2) \\ & = 4^4 T(2^{k-3}) + (2^{k} (k-3)^2 + 2^{k} (k-2)^2 + 2^{k} (k-1)^2 + 2^{k}k^2) \\ ... &= ... \\ & = 4^{i} T(2^{k-i}) + (2^{k} (k-i)^2 + \cdots + 2^{k} (k-1) + 2^{k} k^2) \\ \text{set } i=k & \\ &= 4^{k} T(0) + (2^{2k} 1^2+ \cdots + 2^{2k} (k-1)^2 + 2^{2k}k^2) \\ & = 2^{2k}( 1^2+ \cdots + (k-1)^2 + k^2) \\ \end{align}

\begin{align} ( 1^2+ \cdots + (k-1)^2 + k^2) &= \sum_{i=1}^{k} i^2 \\ &= \frac{ k (k + 1) (2 k + 1)}{6} \end{align}

put back $2^k = n $, and $k = \log_2 n$

$$T(n) = 2^{2k} \frac{ k (k + 1) (2 k + 1)}{6} \in \mathcal{O}( n^2 \cdot \log^3 n)$$

New contributor
kelalaka is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

Just like in the textbook proof of $O(n\mathrm{log}(n))$ complexity for divide-and-conquer quicksort, one only needs to show that the sum of each level never exceed the sum (i.e. the value) at the root.

For simple function like $n$, this is trivial.

For more complicated function like $n^2\mathrm{log}^2(n)$, you need to work.

New contributor
Jan Doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • Hint: $n=a+b$ implies $n^2>a^2+b^2$ all positive, the nasty $log^2$'s can be pushed up to be all equal to $log^2(n)$, so one does not need to care about them any more. – Jan Doe Oct 12 at 7:35

You want to use the Master theorem. Writing $T(n)=aT(n/b)+f(n)$, we get that $a=4$, $b=2$, and $f(n)=n^2\log^2n$. This gives $\log_b(a)=2$. This is the same exponent on $f(n)$, but you have an extra $\log^2n$. This fits case 2 on the Wikipedia page. So we get $O(n^2)$ with an extra $\log^3n$. This gives an overall result of $T(n)=O(n^2\log^3n)$.

New contributor
HackerBoss is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • There is not the Wikipedia version of Master theorem in CLRS book. – Yahya Oct 12 at 0:13
  • No, but there should be a similar version. I just don't have the book to reference, so I had to reference something else. It will be similar – HackerBoss Oct 12 at 2:35

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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