An Algorithm!

Linear search is an algorithm!

The Oxford dictionary defines algorithm as "a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer."

What can we say about the performance of the linear search? Well, let’s consider different cases:

  • If we are lucky, and the target student which we are looking for is the first element in the students array, then we will find it immediately. That’s the best-case scenario.

  • The worst-case is when the target student is not in the roster. The linear search has to go over all the students (their emails) just to report the array does not contain what we are looking for.

The difference between the best and worst case scenarios would be more prominent when the students array is really large and has many elements.

Exercise How long will it take to find a student in each case? (Assume each iteration of the for loop takes $0.004$ milliseconds.)

  1. Roster is used for a required freshman science class at JHU that typically has a few hundreds of 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 of 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 one iteration of the loop to find the student we are looking for. Therefore, it takes $0.004$ milliseconds.

The worst-case scenario will be different:

  • In the first case, we must search $n = 1000$ elements.

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

  • In the second case, we must search $n = 1000000$ elements.

It takes $10^6 \times (4 \times 10^{-3}) = 4000$ milliseconds or $4$ seconds.

Resources

Wikipedia's entry on Linear Search is a good resource for a more in-depth analysis of the topic.