6.2.3. Summary of Worst Case vs. Average Case

Try these first

1. 1.

   What does the term 'input size' refer to?

   Hint

   Consider what you count in arrays and data structures.

2. 2.

   Define 'worst case' in terms of algorithm analysis.

   Hint

   Think about how long an algorithm runs under the most challenging conditions.

3. 3.

   What does the worst-case time complexity indicate?

   • The fastest time an algorithm can complete
   • The average time of all inputs
   • The longest time an algorithm can take

   Hint

   Think about the most time-consuming scenario.

4. 4.

   True or False: Average-case analysis is always easy to compute.

   • True
   • False

   Hint

   What happens when you include varying possibilities?

5. 5.

   Propose an algorithm, and analyze both the worst and average case scenarios, providing a detailed explanation.

   Hint

   Focus on how input size and distribution affects running time.

6. 6.

   Given a set of data, create a probability distribution to simulate an average-case scenario and calculate the expected running time.

   Hint

   Think about averages and sample size.