Exam-style question
Try this first
Analyse the time complexity of merge sort. State the required Big O notation and explain how the Divide and Conquer process relates to this complexity.
Model answer
What a good answer should say
- The time complexity of merge sort is O(n log n).
- The list is divided into smaller parts, creating approximately log n levels of division.
- At each level, the parts are merged while processing the items, giving approximately n work across that level.
- Combining these factors gives O(n log n).
Explanation
Why this works
A complete analysis should identify both the Divide and Conquer structure and the required complexity. The division produces the logarithmic factor, while processing the items during merging produces the n factor.
Common mistake
No common mistake is linked to this question yet.