Time Complexity and Big O
Notation
An analogy to a real-life issue:
This morning I wanted to eat some pizza; So, I asked my brother to get
me some from Dominos, which is 3 km away.
He got me the pizza, and I was happy only to realize it was too little for
29 friends who came to my house for a surprise visit!
My brother can get 2 pizzas for me on his bike, but pizza for 29 friends is
too huge of an input for him, which he cannot handle.
What is Time Complexity?
Time Complexity is the study of the efficiency of algorithms. It tells us how much
time is taken by an algorithm to process a given input. Let's understand this
concept with the help of an example:
Consider two developers Shubham and Rohan, who created an algorithm to sort
‘n’ numbers independently. When I made the program run for some input size n,
the following results were recorded:
Time Taken By Shubham’s
No. of elements (n) Time Taken By Rohan’
Algo
10 elements 90 ms 122 ms
70 elements 110 ms 124 ms
110 elements 180 ms 131 ms
1000 elements 2s 800 ms
We can see that at first, Shubham's algorithm worked well with smaller inputs;
however, as we increase the number of elements, Rohan's algorithm performs
much better.
Quick Quiz: Who’s algorithm is better?
Notation
An analogy to a real-life issue:
This morning I wanted to eat some pizza; So, I asked my brother to get
me some from Dominos, which is 3 km away.
He got me the pizza, and I was happy only to realize it was too little for
29 friends who came to my house for a surprise visit!
My brother can get 2 pizzas for me on his bike, but pizza for 29 friends is
too huge of an input for him, which he cannot handle.
What is Time Complexity?
Time Complexity is the study of the efficiency of algorithms. It tells us how much
time is taken by an algorithm to process a given input. Let's understand this
concept with the help of an example:
Consider two developers Shubham and Rohan, who created an algorithm to sort
‘n’ numbers independently. When I made the program run for some input size n,
the following results were recorded:
Time Taken By Shubham’s
No. of elements (n) Time Taken By Rohan’
Algo
10 elements 90 ms 122 ms
70 elements 110 ms 124 ms
110 elements 180 ms 131 ms
1000 elements 2s 800 ms
We can see that at first, Shubham's algorithm worked well with smaller inputs;
however, as we increase the number of elements, Rohan's algorithm performs
much better.
Quick Quiz: Who’s algorithm is better?
