What is Big O Notation

For Complete YouTube Video: Click Here

In this class, we will try to understand What is Big O Notation.

The definition of Asymptotic notation was explained clearly in our previous class.

What is Big O Notation

The definition of the Big O Notation is as shown below.

The function f(n) = O(g(n)) if and only if there exists positive constants c and n0 such that f(n) <= c * g(n) for all n, where n >= n0.

The above definition states that function f(n) can be expressed as O(g(n)) (Big O of g of n) when f(n) is less than or equal to some constant c * g(n) for all the values of n where n is greater than or equal to n0.

This definition is proven for any function f(n). In our course, we consider f(n) as the time complexities of the algorithms.

To understand the definition better, we will consider the example shown below.

For example, the time complexity of an algorithm is 3n + 2.

This 3n + 2 can be expressed in Big O notation if we can prove that 3n + 2 is less than or equal to c*g(n) for all the values of n where n >= n0.

Consider 3n + 2 <= 4n for all the values of n >= 2 (n0 = 2).

The above expression is true for all the values of n >= 2.

If n = 2 then 3n + 2 <= 4n is true.

If n = 3 then 3n + 2 <= 4n is true.

Simillarly, for n = 10, 3n + 2 <= 4n is true.

In such cases, we can say that 3n + 2 = O(g(n)).

What does the Big O notation describe an algorithm?

With the Big O notation, we will get the upper bound for the function.

For all the values of n >= 2, 3n + 2 will never cross 4n.

The image below shows the Big O notation on a graph.

For a clearer and better understanding, click on the top and learn for free.