Algorithms: Design and Analysis, Part 1 - Exam Question 3

Problem:

What is the asymptotic worst-case running time of MergeSort, as a function of the input array length $ n $?

Solution:

Actually all recursion levels will take $ \theta(n) $ time to create the merged arrays, so the time is obviously $ \theta(n \log n) $ time.