TIME COMPLEXITY AND BIG O NOTATION
Hello everyone,
So, today we learn about time complexity concepts and Big O notation.
One day, in the morning, i wanted to eat pizzas ,so i asked my sister to get me some pizzas from Dominos (3 Km away from my place).She got me the pizza and I was happy only to realize it was too less for 29 friends ,who came to my house for a visit.My sister can get pizzas for me on her bike but pizza for all the friends is too huge of an input for her which she can’t handle .
- 2 PIZZAS — — →:) OKAY! NOT A PROBLEM
- 68 PIZZAS — — →:( NOT POSSIBLE! IN SHORT DURATION OF TIME
NOW,
WHAT IS TIME COMPLEXITY?
- It is a study of efficiency of algorithms.
Time complexity = How time taken to execute an algorithm grows with the size of the input.
- Consider 2 developers who created an algorithm to sort ’n’ numbers. Shivi and Daisy did this independently.
- For input size n , following results were recorded .
In the above observations,we can see that initially Shivi’s algorithm was shining for smaller input but as the number of elements increases Daisy’s algorithm looks good.
#QUICK QUIZ: Who’s algorithm is better ?
Time Complexity:
* Sending God Of War 4 to a friend
Let us say you have a friend living 5 km away from your place. You want to send him a game.Final exams are over and you want him to get this 60 GB file from you. How will you send it to him?
NOTE:- Both of you are using JIO 4G with a 1 Gb/day data limit.: Sending God Of War 4 to a friend
- The best way to send him the game is by delivering it to his house.
- Copy the game to a hard-disk and send it.
Will you do the same for sending the game like minesweeper which is in KBs of size? No, because you can easily send it via the internet.
- As the file size grows, time taken by online sending increases linearly — O(n’)
- As the file size grows, time taken by physical sending remains constant. O(n0) or O(1).
Calculating Order in terms of Input Size:
- In order to calculate the order, the most proper term containing n is taken into account. (Here n = Size of input)
- Let us assume that formula of an algorithm in terms of input size n is:-
Note, that these are the formulas for the time taken by them.
Visualizing Big O:
If we were to plot O(1) and O(n) on a graph, they will look something like this:
BIG-O Complexity Chart
- Have a look ,
Time complexity can sometimes be very challenging to understand.This notes throws light on the basics on Time complexity and Big O notation.Hope you guys understand . In my upcoming notes, i will clear the concepts of other notations .
STAY FIT STAY SAFE
THANK YOU.
