What is the run time of Merge Sort algorithm in terms of Big O? a. O(logN) b. O(N) c. O(N!) d. O(NlogN) e. O(N^2)

Understanding Merge Sort Time Complexity

Merge Sort is a classic sorting algorithm that follows the divide and conquer paradigm. To determine its runtime complexity, we analyze how it operates:

1. Dividing the List: The array is divided into two halves.
2. Conquering: Each half is sorted recursively, using the same merge sort algorithm.
3. Merging: Finally, the two sorted halves are merged together to form the sorted array.

Relevant Concepts

The critical aspect of Merge Sort's efficiency is in how the problem scales with the size of the input $N$:

• The array is split in half repeatedly, leading to a logarithmic factor of $\log N$ due to the depth of the recursive calls.
• At each level of recursion, the merging of the halves takes linear time $O(N)$.

Analyzing Merge Sort's Time Complexity

To express this in Big O notation:

• The depth of the recursion is $O(\log N)$.
• The work done at each level is $O(N)$.

Combining these two components gives us: $\text{Total Time} = O(N) \times O(\log N) = O(N \log N)$

Thus, the runtime for Merge Sort can be succinctly represented as $O(N \log N)$.

Verifying and Summarizing

• Dividing the Array: Takes $\log N$ splits.
• Merging: Each level of recursion requires $O(N)$ time for the merging process.

Hence, both the recursive nature and the merging step confirm that the total runtime complexity of Merge Sort is indeed $O(N \log N)$.

Final Answer

The run time of the Merge Sort algorithm in terms of Big O is: d. O(N log N).