malcolm malcolm - 7 months ago 15
Java Question

How to find out whether a given function is O(n)?

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


I know that time complexity of O(n) depends upon on the number of elements, so as the number of elements increases the time it takes to finish an operation increases. According to this logic, is it right to say that a and c take time complexity of O(n)?

Answer

Consider the definition of O(n), which is that for some function f(n) there must be two positive constants, c and k, such that c > 0, k > 0, n >= k, and 0 <= f(n) < cn. If we can show that constants c and 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

Lets set 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

Lets set 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 c and 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 n^2, lgn, nlgn are all interesting boundaries that will probably appear on your future tests.

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