Solution of CLRS question 4.6-2

Question

I am trying to solve the 4.6-2 question in CLRS book which is

$T(n)= aT(n/b) + \Theta(n^{\log_ba}\lg^{k}n)$

While solving the above equation I reach the following point:

1. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n/b^j)\right) $

when I searched online, I saw people have solved this as below:

2. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- \lg^k(b^j)\right) $
3. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- o(\lg^k(n))\right) $
4. $T(n)= n^{\log_ba} + n^{\log_ba}( \log_bn \cdot \lg^k(n)+ \log_bn \cdot o(\lg^k(n))) $
5. $T(n)= n^{\log_ba} + \Theta(n^{\log_ba}\lg^{k+1}(n)) $

I did not understand the following points:

• $ \lg^kn/b^i = (\lg n - \lg b^i)^k $, then how in equation 2, we can have power k on individual logs?
• In equation 4, after calculating the summation, how did the subtraction between logs turn to sum?
• There is a small o in equation 4, then how can we write theta in equation 5.

Answer 1

The first point seems like a mistake. Find a different solution.

For the second point, $o(f(n))$ often refers to a function whose absolute value is $o(f(n))$. So $-o(f(n))$ and $o(f(n))$ are really the same thing. For example, you can write $n - 1 = n + o(n)$.

For the third point, here is a simpler example: $n + o(n) = \Theta(n)$. You can check that if $|f(n)|/n \to 0$ then $(n + f(n))/n \to 1$, and in particular $n + f(n) = \Theta(n)$.