# Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?

The original problem I was solving was what would the time complexity of a merge sort algorithm be, if it used a merge algorithm with complexity $$\Theta(n^2)$$ instead of $$\Theta(n)$$. The solution says the time complexity will be $$\Theta(n^2)$$, but I don't understand why it's not $$\Theta(n^2\log n)$$? I tried using a recurrence tree, and since it looks similar to the one for a linear merge method, just with $$T(n)=2T(n/2)+\Theta(n^2)$$ instead of $$T(n)=2T(n/2)+n$$. So why does it not give a similar solution? I understand that the master theorem can be used to prove this, but I don't understand why the approach used when finding a runtime for merge sort with linear merge doesn't work here.

Because the work done is $$T(n) = 2T(n/2) + n^2 \leq \sum_{i=0}^{\log_2 n} 2^i \left(\frac{n}{2^i}\right)^2 = n^2 \sum_{i=0}^{\log_2 n} \frac{2^i}{2^{2i}} = O(n^2).$$

Try for yourself to see what happens when you remove the factor squared in the summation.

Assume $$n=16$$.

Standard MergeSort involves the cost $$16+2\cdot8+4\cdot4+8\cdot2$$. If we divide by $$n$$, $$1+1+1+1$$.

"Quadratic" MergeSort involves $$256+2\cdot64+4\cdot16+8\cdot4$$. If we divide by $$n^2$$, $$1+\dfrac12+\dfrac14+\dfrac18$$.

Do you see the patterns ?

In the recursion tree, the cost of the top level (i.e. level 0) is $$n^2$$. There are two nodes in level $$1$$, each having a cost of $$(n/2)^2$$; hence, the total cost of level $$1$$ is $$n^2/2$$. In level $$2$$, there are $$4$$ nodes, each with a cost of $$(n/4)^2$$; hence, the total cost of level $$2$$ is $$n^2/4$$. Thus, each level has a cost $$n^2$$ times a coefficient, but these coefficients decrease geometrically, i.e. the coefficients are $$1, 1/2, 1/4, 1/8$$, etc. Hence, the total cost of all levels is $$n^2 (1+1/2 + 1/4 + \cdots) \le 2n^2$$, and hence the total cost is $$\Theta(n^2)$$.

Thus, even though the formula for the total cost has on the order of $$\log n$$ terms and each term is of the form $$n^2$$ times a coefficient, the sum of these coefficients is bounded from above by a constant. Recall that constants are subsumed in asymptotic notation.

More generally, when the common ratio $$r$$ is less than $$1$$, we have that $$1+r+r^2 + \cdots + r^{\log_2 n} = \Theta(1)$$, i.e. the first term $$1$$ dominates the sum. This is why, in this case of the Master theorem, the total cost $$n^2 (1+r+r^2+\cdots+r^{\log_2 n})$$ is dominated by the first term; equivalently, the total cost of all levels of the recursion tree is dominated by the top level.