Best vs. Worst Case

  • Differentiate between the best-case and the worst-case scenarios for binary search runtime
  • Recognize the speed difference between linear search and binary search

Let's rework the last exercise for Binary search.

Exercise How long will it take to find a student in each case? (Assume the students array is sorted and each step through the search process takes $0.004$ milliseconds.)

  1. Roster is used for a required freshman science class at JHU that typically has a few hundred students (all sections combined); let's round that up to 1000 students!
Best-caseWorst-case



  1. Roster is used for a JHU Engineering for Professional MOOC (Massive Open Online Course) that has a few hundred thousand students (all cohorts combined); let's round that up to a million!
Best-caseWorst-case



Solution

The best-case scenario for both cases is the same: it takes $0.004$ milliseconds to find the student we are looking for.

The worst-case scenario:

  • In the first case, for $N = 1000$ it take approximately $\log_2 (1000) \approx 10$ steps.

It takes $10 \times (4 \times 10^{-3}) = 0.04$ milliseconds.

  • In the second case, for $N = 10^6$ it take approximately $\log_2 (10^6) \approx 20$ steps.

It takes $20 \times (4 \times 10^{-3}) = 0.08$ milliseconds.

For linear search, when the size of the array increased by a factor of $1000$, the time (for worst-case) increased by the same factor of $1000$ (a linear scale, hence the name linear search). However, for binary search, the same increase in size only doubled the runtime.

Resources