2
$\begingroup$

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.

$\endgroup$

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 ?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.