I was given the following question in my test:
Which of the following are in O(n)?
a) n + lgn
b) n + 2n
c) n + n^2
d) 1000n + 4500lgn + 54n
Consider the definition of O(n), which is that for some function f(n) there must be two positive constants,
k, such that
c > 0,
k > 0,
n >= k, and
0 <= f(n) < cn. If we can show that constants
k exist then the function is O(n) (and if those constants don't exist then the function is actually larger than O(n)).
Lets look at
F(n) = n + lg(n). Is this O(n)? If so, then we shouldn't have any trouble finding values for c and k.
0 <= f(n) <= cn 0 <= n + lg(n) <= cn
k to 2 and consider the base case where n is 2 (because n >= k).
0 <= 2 + lg(2) <= c * 2 0 <= 2 + 1 <= 2c 0 <= 3 <= 2c 0 <= 3/2 <= c
Lets see how the function behaves as n increases (lets set n = 4 and see what happens).
0 <= 4 + lg(4) <= c * 4 0 <= 4 + 2 <= 4c 0 <= 6 <= 4c 0 <= 6/4 <= c 0 <= 3/2 <= c .. take a look at that, it doesn't matter how large n becomes, c is 3/2
So we have found our constants (c=3/2 and k=2) and so this function is O(n) by the formal definition.
Lets look at
F(n) = n + n^2. Is this O(n)? It should be pretty obvious that its not, it is actually O(n^2), but lets see if we can find values c and k anyhow.
0 < f(n) < cn 0 <= n + n^2 <= cn
k to 2 again and consider the base case where n = k.
0 <= 2 + 2^2 <= c*2 0 <= 2 + 4 <= 2c 0 <= 6 <= 2c 0 <= 3 <= c .. so IF this is O(n), c is at least 3
Lets see what happens as n increases (now n = 4)
0 <= 4 + 4^2 <= 4c 0 <= 4 + 16 <= 4c 0 <= 20 <= 4c 0 <= 20/4 <= c 0 <= 5 <= c .. last time c was 3, now its 5 ... as n increases, c is not constant!
This function is not O(n) - we can't find constant values
k because they simply don't exist.
Consider f(n) = 5n ... this is O(n) (in this case its obvious that c is 5). Consider f(n) = n * n .. this isn't O(n) (c would be equal to n which is not constant). What we are really saying is that our function f(n) is bounded by another function g(n) multiplied by some constant. When we ask if a function is O(n) we let
g(n) = n, but
nlgn are all interesting boundaries that will probably appear on your future tests.
n + n^2 O(n^2)? You shouldn't have trouble finding values
c > 0 and
k > 0,
n >= k, such that
0 <= f(n) <= cn^2.
Take a look at https://xlinux.nist.gov/dads//HTML/bigOnotation.html for further reading.