# Proof that n + (logn)^2 is O(n)

The question is:

Show that n + (logn)^2 is O(n), so n + (logn)^2 <= c * n.

I can't find n1 and c such that it is true for all n > n1.

## Answers

**n** < **( log n)2** for values of

**n**< 0.49

**Graph**:

blue line => **n** and the green line => **( log n)2**)

But for large **n**, **( log n)2** is negligible:

ThereFore, answer is **O(n)**

We can prove that logn^2 < n for large enough n.

You can do this by doing limit of n goes to infinity for logn^2 / n. You can solve this limit by derivating numerator and denominator. You get 1/n. We know that limit of 1/n, n goes to infinity, is 0.

Above implies that logn^2 < n, for large enough n, otherwise limit could never be 0.

As logn^2 < n for large enough n this implies log2^n = O(n).