# Solution of CLRS question 4.6-2

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:

1. $$T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- \lg^k(b^j)\right)$$
2. $$T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- o(\lg^k(n))\right)$$
3. $$T(n)= n^{\log_ba} + n^{\log_ba}( \log_bn \cdot \lg^k(n)+ \log_bn \cdot o(\lg^k(n)))$$
4. $$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.
• Why solve it, when the master theorem already solves it for you? – Yuval Filmus May 21 '20 at 12:26
• As per the CLRS book , master theorem can be applied here as f(n) contains lgn. – V K May 21 '20 at 15:34
• The Wikipedia version applies. I don't see why you have to limit yourself to what's in a particular textbook. When your boss asks you to program something, will you tell them it's not in the textbook? – Yuval Filmus May 21 '20 at 15:36

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

• I am little confused on $n+o(n)=Θ(n)$. Can you please explain this. $o(n)$ represents an anonymous function strictly larger than n. Let it be $g( n)=n^2$. So how is $n+n^2=\theta (n)$. I might be missing something. – rsonx May 21 '20 at 15:49
• Actually, $o(n)$ represents an anonymous function strictly smaller than $n$. You are thinking about $\omega(n)$. The way to remember this is: little $o$ is a stricter version of big $O$, and the same for little $\omega$ and big $\Omega$. – Yuval Filmus May 21 '20 at 15:54
• Now I understand. Thanks for clarification. – rsonx May 21 '20 at 16:36