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.
  • $\begingroup$ Why solve it, when the master theorem already solves it for you? $\endgroup$ – Yuval Filmus May 21 '20 at 12:26
  • $\begingroup$ As per the CLRS book , master theorem can be applied here as f(n) contains lgn. $\endgroup$ – V K May 21 '20 at 15:34
  • $\begingroup$ 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? $\endgroup$ – 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)$.

  • $\begingroup$ 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. $\endgroup$ – rsonx May 21 '20 at 15:49
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus May 21 '20 at 15:54
  • $\begingroup$ Now I understand. Thanks for clarification. $\endgroup$ – rsonx May 21 '20 at 16:36

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.