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.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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 ?
$\begingroup$
$\endgroup$
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.
