Question $10$: Amortized Analysis $(5$ points$)$

$($a$)$ What is amortized analysis, and how does it differ from worst$-$case and average$-$case analysis? $(3$ points$)$

$($b$)$ Give an example of an algorithm where amortized analysis is useful, and briefly explain how it works. $(2$ points$)$

Part $4$: Practical Questions $(25$ points$)$

Question $11$: Divide$-$and$-$Conquer Algorithm Implementation $(10$ points$)$

Task: Write a Python implementation of the Merge Sort algorithm. Your function should divide the list into smaller subproblems, sort each subproblem, and merge them back together. Include comments to explain each step. $(5$ points$)$

Task: Analyze the time and space complexity of your Merge Sort implementation. $(5$ points$)$

Question $12$: Recursion and Complexity $(10$ points$)$

Task: Write a Python function to calculate the nth Fibonacci number using a recursive approach. Then, analyze the time complexity of this recursive implementation. $(5$ points$)$

Bonus Task: Implement a memoized version of the Fibonacci function to improve the time complexity. Compare the time complexities of the recursive and memoized versions. $(5$ bonus points$)$

Question $13$: Amortized Analysis Example $(5$ points$)$

Task: Simulate a dynamic array in Python that resizes itself when it reaches capacity $($doubling its size$).$ Implement a function to perform a sequence of insertions and print the array's capacity after each insertion. Analyze the amortized cost of insertions and explain how the amortized analysis ensures that the average insertion time is $O(1).(5$ points$)$