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

1

Expert's answer

2019-02-22T05:38:07-0500

@$(\log^2n-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}@$

## Comments

## Leave a comment