Answer to Question #85285 in Algorithms for Mlk

Question

Prove that n + log2n = O(n) by showing that there exists a constant c > 0 such that n + log2n ≤ cn.
(note that log2n means (log n)2.)

Answer 1

$$(\log^2⁡n-n)'=2 \log ⁡n \times 1/n-1=2 ((\log ⁡n-n))/n\le0,\quad n\in\mathbb{N}$$ $$(\log ⁡n-n)'=1/n-1\le0$$ $$\log^2 n \le n$$ $$n + \log^2 n \le n + n = 2n,\quad n\in \mathbb{N}$$