12.1.6. Recursion Analysis

Try these first

1. 1.

   What does Insertion Sort do?

   Hint

   Think about how you sort cards in your hand.

2. 2.

   Define time complexity.

   Hint

   Consider how the time increases with more data.

3. 3.

   What is the time complexity of Insertion Sort?

   • O(n)
   • O(n log n)
   • O(n^2)

   Hint

   Consider how many comparisons you might have to make with reversed data.

4. 4.

   True or False: Insertion Sort can be faster than selection sort on nearly sorted lists.

   • True
   • False

   Hint

   Think about how well it handles existing order.

5. 5.

   Implement Insertion Sort in a programming language of your choice, both iteratively and recursively. What differences do you observe in performance?

   Hint

   Focus on measuring the execution time with varying list sizes.

6. 6.

   Create an input case for Insertion Sort that highlights its worst-case time complexity. Explain your reasoning.

   Hint

   Think about how selections each time for the next element will be maximum.