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


Need Your Help

How to scale and set coordinates of MediaView?

java javafx-2

I would like to embedd a video in my JavaFx 2.x scene and also resize it and relocate it to my needs. The problem I'm having is following. If I build a MediaView component and then translate X or Y