BigO notation

What is a Big O notation?

 

Big O notation basically describe the time complexity of a program. Feeling difficult to understand Let's see with an example.

 

Suppose that you are transferring a file of few kilo-bytes or even 1GB to the friend who is a far distant place which mode of transfer will you prefer?

The short and easy answer would be just sent it by a mail or any FTP(file transfer protocol)

 

Now I am modifying a bit.

Suppose that you are transferring a file of 1 TB to the friend who is a far distant place which mode of transfer will you prefer?

You will be shock to listen but traveling by plane to transfer that file at the moment is much faster than transferring it by any FTP or mail if that is too urgent to do so.

 

So, from the above two questions we can conclude that as the file size increases the time to transfer the file also increases in computers. while transferring it by plain will always remain the same in both the above scenarios  so we can say the time complexity for transferring the file through mail will be O(N) while by plane it will be O(1).

 

Big O notation help us to optimize the algorithm depending upon the situation or problem asked it not always better to use an algorithm with lower time complexity or higher time complexity without analyzing the  constrains for which we are solving that problem.

Types of notation

1. Big O: It is the complexity that is going to be less than or equal to worst case    complexities.

2. Big Ω: It is the complexity that is going to be at least more than the best case    complexities.

3. Big Θ: It is the complexity between the bonds of worst and best case complexities.