Chapter 5: Asymptotic Notation Big O

In this chapter we shall learn about below topics:

Big O notation is generally used to calculate the complexity of an algorithm, because we want to know on how the algorithm will perform when the input size is increased.

In this chapter we shall know about Big O notation in detail.

To say a function f(n) is equal to O(g(n)), if there is a constant “C” and “n0” such that the function f(n) will always be less that “c * g(n)”, can be written as “f(n) < c*g(n)”.

It means that the function f(n) will not go above the function g(n) for a large value of n. Hence we can consider the function “g(n)” as upper bound for the function f(n).

We try to do this because, we know the rate of growth of the function “g(n)” [remember in chapter 3] and hence we try to reduce the function “f(n)” to a known value of rate of growth.

Let us understand the above definition with the help of examples:

f(n) = 6n + 7
g(n) = n

Now we need to check if f(n) is O(g(n)).

i.e we need to check if f(n) = O(n).

So the function 6n + 7 will be equal to g(n), if we can find constants C and n0 such that 6n + 7 <= C*n for all n>= n0.

By analysis we get

When n =5 and C = 8, we can satisfy the condition 
6n + 7 <= C * n For all n>= n0
6*5 + 7 <= 8 *5
37 <= 45 for all n >= 5

Hence we can say that the function 6n + 7 is O(n).

Note: There can be many values for C and n0.

f(n) = 3n^2 + 4n + 7
g(n) = n^2

We have to prove that the function f(n) is of order O(n^2).

When C= 5 and n0 = 6

We satisfy the condition

3n^2 + 4n + 7 < 5n^2 for all n >= 6;

So like I said in previous topics, we try to reduce the function f(n) to known values of g(n), so that it will easy for us to calculate the running time of the algorithm.

1. f(n) = 10 is of order O(1)

2. f(n) = 6n^3 +  2n^2+  3 is of order O(n^3). Because for larger value of n, (2n^2 + 3) will be negligible.

3. f(n) = 8 log n+ 2n + 5 is of order O(n). This is because the rate of growth of n is greater than log n.

Hence we usually see below graph for O(n).