0
$\begingroup$

In a book on algorithms I read that $n^2 (1+\log n)$ as $n$ approaches infinity is approximated to $n^2 \log n$.

I am not sure if I understand reasoning in this. Is it because $1+\log n$ grows so fast that $\log n$ could substitute it, so that +1 makes no big difference and so is ignored?

$\endgroup$
0
$\begingroup$

Yes, for large $n$ you can consider for all practical purposes that $ n^2 (1+ \log n) \approx n^2 \log n$. Is is like you say, as $n$ increases the +1 becomes more and more insignificant (to quantify how insignificant, you can compute the relative error).

$\endgroup$
  • $\begingroup$ I also wanted to vote up, but it does not let me with reputation less than 15! Anyway thanks a lot, also for the edit. $\endgroup$ – higraphs Feb 5 at 17:20
  • $\begingroup$ You're welcome! $\endgroup$ – PierreCarre Feb 5 at 17:45

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.