Asymptotic Notations- Big O Notation [O]

We always hear below common terms in the world of computer science: 

Data Structure- It defines how the data is arranged in computer’s memory.  For example- arrays, stacks , linked lists are few of the popular data structures. 

Algorithm- It is a set of instructions used to manipulate data structures. For example- sorting algorithm, searching algorithm etc.

Time Complexity- It is a measurement of rate of growth of time taken by any algorithm with respect to the increase in input size.

Space Complexity- Similar to the time complexity, it is a measurement of rate of growth of memory space taken by any algorithm with respect to the increase in input size.

Asymptotic Notation- It is a standard used for determining time/space complexities of an algorithm.

There are three basic asymptotic notations-

1. Big O Notation [O]
2. Big Omega Notation [Ω]
3. Big Theta Notation [θ]

1. Big O Notation [O]

This notation represents tight upper bound of the given function.

Analytically we say as: f(n) belongs to O(g(n)) as there exists c > 0 (e.g., c = 1) and n0 (e.g. n0 = 5) such that f(n) ≤ cg(n) whenever n ≥ n0.

Lets see it through an example-

We have another function f(n) = 5n+4. Lets find the tightest upper bound of this function. By tightest upper bound I mean we have to find an another function (say g(n))  that will be always higher when we multiply g(n) by some constant (say c) and add some value of n (say n0) to it.

By looking to f(n) we can say that if we have a function g(n) = 6n then it will be the tightest upper bound of f(n). In other words: f(n) ≤ cg(n) for c=6 & n0=4. To represent it in Big O we say f(n) = O(n) & it is read as "f of n is big oh of g of n".

Now you might say what if you have taken g(n) = 6n² or g(n) = 6n³ ?

Well, you are right! And in this case complexity will be O(n²) and O(n³) respectively because f(n) will always be less than or equal to g(n) for any value of n.

But since we use Big O notation to represent tightest upper bound of the function, we will say f(n) = O(n) instead of O(n²) or O(n³).

Big O notation is usually used to specify time/space complexity of the given algorithm in worst case scenario. Worst case scenario is the situation when algorithm takes maximum time to run or maximum memory during it's execution.

In the next post we will see Big Omega & Theta Notations.