Big O

This is such an important concept that we are going to dedicate an entire post to it.

Big O is used to describe the efficiency of algorithms.

An Analogy

🤔Suppose you got a file on a hard drive and you want to send it to a friend living in another state so the way you can send it is either through the internet or by any mode of transportation.

If you send it by internet the time taken to reach the file will be based on the size of the file so we can say that the time taken to reach the file is linearly dependent on the size of the file in terms of Big O we can say it is O(n).

If we send by any mode of transportation the time taken to reach the file will always be the same no matter how huge the file so in terms of Big O we can say it is O(1).

Just a recall from academics Big O is the worst case, Big Omega is the best case and Big theta is the average case.

💪To know the efficiency of an algorithm it's always best to consider the worst-case that is why we can find Big O everywhere.

Time Complexity & Space Complexity

⌚Time to run a program is known as Time Complexity to represent the run time we use notation like Big O. 

Space Complexity is a parallel concept to time complexity, If we want to create a 1D array of n size then we need O(n) space.

How to calculate complexity?

• Drop the constants.

Suppose if we found complexity is O(n+32) we have to write it is O(n).

• Drop the Non-Dominant Terms

Suppose if we found complexity as O(n*n + n*n*n + 54n+ 64n*n+ 1089) we have to write it as O(n*n*n).

Amortized time

When the worst case is happening really and some other case better than the worst case is happening most of the time so that case is known as amortize time.

Suppose in ArrayList of current size 4, we want to insert an element so we can insert an element at a time of O(1) for (0-3 index) but at 4th index, we have to create a new ArrayList of double size and add all the elements of the previous ArrayList and then insert the element at 4th index which will take time of O(n) and after that, we can insert element again at the time of O(1) till the index 7th.

So here the time complexity is O(n) but it's very rare it's happening once in a while so the worst case for insertion in ArrayList is O(n) but to indicate that the worst case is very rare we use Amortize time here amortize time is O(1).

Popular Complexity

• O(n) - when time is increasing linearly (ex- iterating 1D array of size n)
• Log N - when no of calls is getting halved in each iteration ( ex- binary search)
• 2^N - when no of calls is getting doubled in each iteration  (ex - binary tree)