Before we start, my textbook declares lgn as base two.

I only have one question, how did log2 become n (both highlighted in yellow in the picture)? Is it because log2 = 1, which is too small to even matter?

enter image description here

  • 2
    $\begingroup$ 1) In which way is this a computer science as opposed to a pure mathematics question? Seems to me that this is about middle-grade arithmetics, which is probably a better fit for Mathematics. 2) Please get rid of the image and use Markdown and MathJax to reproduce its content. 3) You need to give attribution. Which book by whom are you referencing? $\endgroup$ – Raphael Feb 7 '17 at 10:56
  • 1
    $\begingroup$ "how did log2 become n" -- it didn't. $\endgroup$ – Raphael Feb 7 '17 at 10:57

Since we're using base-$2$ logs, $\log2=1$, so $$n(\log n-\log 2) = n\big((\log n)-1\big)=n\log n -n\,.$$

All of the stages of the calculation are written as equalities, so nothing should be being discarded as too small to matter (and nothing is).


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.