Course Content

Best Case, Worst Case and Average Case Analysis of an Algorithm (With Notes)

Either you can download the handwritten notes in pdf (Link is given at the end of the page) or you can read them on this site itself.

Sometimes we get lucky in life. Exams canceled when you were not prepared, a surprise test when you were prepared, etc.   → Best case

Sometimes we get unlucky. Questions you never prepared asked in exams, rain during the sports period, etc.  → Worst case

But overall the life remains balanced with the mixture of lucky and unlucky times.  → Expected case

 

Analysis of a search algorithm:

Consider an array that is sorted in increasing order.

1

7

18

28

50

180

 

We have to search a given number in this array and report whether it’s present in the array or not.

Algo 1 – Start from the first element until an element greater than or equal to the number to be searched is found.

Algo 2 – Check whether the first or the last element is equal to the number. If not find the number between these two elements (center of the array) if the center element is greater than the number to be searched, repeat the process for the first half else repeat for the second half until the number is found.

 

Analyzing Algo 1

If we really get lucky, the first element of the array might turn out to be the element we are searching for. Hence we made just one comparison.

Best case complexity = O(1)

If we are unlucky, the element we are searching for might be the last one.

Worst-case complexity = O(n)

For calculating the average case time, we sum the list of all the possible case’s runtime and divide it with the total number of cases. (Sometimes calculation of average-case time gets very complicated)

Analyzing Algo 2

If we get really lucky, the first element will be the only one which gets compared

Best case complexity = O(1)

If we get unlucky, we will have to keep dividing the array into halves until we get a single element (the array gets finished)

Worst-case complexity = O(log n)

 

What log(n)? What is that?

Log n simply means how many times I need to divide n units such that we cannot divide them (into halves) anymore.

Space Complexity

Time is not the only thing we worry about while analyzing algorithms. Space is equally important.

Creating an array of size n (size of the input) O (n) Space

If a function calls itself recursively n times its space complexity is O (n). :)

 

Quiz Quiz: Calculate space complexity of a function that calculates the factorial of a given number n.

 

Why can’t we calculate complexity in seconds?

→Not everyone’s computer is equally powerful.

→Asymptotic analysis is the measure of how time (runtime) grows with input.

 

Download Notes

Be the first person to comment!

Comments(0)

Resources

  1. Best_Worst_Average - Download here
  2. - Download here

Course Announcements

Any Course related announcements will be posted here