Need for Speed
Explore the concept of algorithm performance by comparing time and space complexity using upper and lower bounds. Understand why stop-watch timing is insufficient, learn about best, worst, and average case scenarios, and grasp the need for a mathematical framework to uniformly compare algorithms regardless of external factors.
We'll cover the following...
The Race Track
Let's say you are a participant in your school's annual sports competition, which includes the 100-meter dash. You are a fast runner but not the fastest. You know Milkha is the fastest runner in the school and will probably finish first on the day of the race. The night before the competition you explain your predicament to your mother. She innocently asks, "But how fast is Milkha?" She hasn't seen you or Milkha run, and has no clue about your respective sprinting abilities. You reply back "Faster than me.". She quizzes back "How much faster than you?". You quip back "Faster than me, but definitely slower than Usain Bolt," someone your mother has seen run. By providing these comparisons to your mother, you are essentially setting a lower and upper bound on the running abilities of Milkha. Milkha will definitely run definitely faster than you, but will surely be slower than Usain Bolt.
You can also compare yourself directly with Usain Bolt and say you run slower than him, but then you are not bounding your skill tightly enough; you might as well say you run slower than the speed of light. That statement, ...