Why does memoization not improve Merge Sort runtime?
I have this question from Assignment task. But, as far as I know, Merge Sort uses a separation and subjugation approach (without overlapping subtasks), but Memoization is based on dynamic programming (with overlapping subtask). I know that Merge Sort runtime is O (nlogn).
I even searched in search engines and there is no result for this question. Is this question wrong? If this sounds wrong, but why did the professor ask the wrong question in the assignment? If the question is not wrong or my understanding of the question, Merge Sort and Memoization is wrong, how can I answer this question?
source
share