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.
n < (log n)2 for values of n < 0.49
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).