6.2. Worst Case and Average Case Analysis

Try these first

1. 1.

   Define input size in relation to algorithms.

   Hint

   Think about how you measure data for sorting or searching.

2. 2.

   What is the worst case for a linear search in an unsorted array?

   Hint

   Consider how many items need to be checked.

3. 3.

   What does worst case analysis measure?

   • The average performance of an algorithm
   • The scenario that takes the most time
   • Performance under best conditions

   Hint

   Think about the definition of worst case.

4. 4.

   True or False? Average case analysis is easier to compute than worst case analysis.

   • True
   • False

   Hint

   Which analysis is usually more straightforward?

5. 5.

   Consider two sorting algorithms: one with an average case of O(n log n) and another with a worst case of O(n^2). Describe a scenario where the better average case algorithm might perform worse in execution.

   Hint

   Think about how the size of the dataset affects performance.

6. 6.

   Given an unsorted list of numbers, develop an algorithm to find the maximum number. Analyze its worst case and average case performance.

   Hint

   What happens if the maximum number is always at the end?