Naive recursive Fibonacci takes exponential time; adding memoisation makes it linear. Why does storing results change the growth class so dramatically?

B. Because the naive version recomputes the same subproblems exponentially.

Draw the call tree and the waste is visible: about 2ⁿ nodes containing only n distinct values. Memoisation removes duplication rather than speeding anything up, so the work becomes proportional to the number of distinct subproblems. That identifies when the technique applies, overlapping subproblems, plus optimal substructure. Merge sort's halves are all distinct, so there is nothing to reuse.