1
$\begingroup$

Assuming that the worst case running time of merge sort can be described with this recurrence:

$\ T(n) = \begin{cases} \theta(1) & \text{if }n = 1\\ 2T(\frac{n}{2}) + \theta(n) & \text{if } n\gt 1 \end{cases} $

Introduction to Algorithms says that it is possible for the same constant $\ c $ to represent the time required to solve problems of size $\ 1 $ as well as the time per array element of the divide and combine steps, so that

$\ T(n) = \begin{cases} c & \text{if }n = 1\\ 2T(\frac{n}{2}) + cn & \text{if } n\gt 1 \end{cases} $

How is there a constant $\ c $ that can represent both times? Shouldn't the proper way to describe the recurrence be

$\ T(n) = \begin{cases} a & \text{if }n = 1\\ 2T(\frac{n}{2}) + bn & \text{if } n\gt 1 \end{cases} \text{where }a\ll b $

If the answer is dependent on the psuedocode provided in the book, I'll post it here. However, there is a single if statement in a trivial mergesort (size 1). Surely, the cost of that single if statement can't be the same as the sum of the costs of all the steps taken in the merge step, as well as the constant-time division of the problem into smaller problems?

Sorry if this has been asked before.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Nitpick: Are they really talking about time? If they are actually counting some operation, it's well possible (if unlikely) for the same constant to show up in both places.

How is there a constant c that can represent both times?

It (probably) can not. This is a simplification done with the goal in mind: derive a $\Theta$-bound.

Apply the Master theorem to both candidate recurrences; you'll note that the result stays the same. CLRS know this from experience, so they simplify the recurrence a-priori.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ah, that is one important distinction that I missed. They are in fact talking about "basic steps". But now I'm thinking this: in the case of n = 1, a single if statement is executed. Meanwhile, multiple assignments and comparisons are made for each array element in merge. Is it actually possible for them (the amount of basic steps in the if statement and the amount of basic steps for each array element in merge) to still be the same in some situation? $\endgroup$
    – Alexander M
    Nov 2, 2017 at 12:17
  • $\begingroup$ @AlexanderM In principle, sure. I haven't looked at the specific algorithm you're investigating, though. $\endgroup$
    – Raphael ♦
    Nov 2, 2017 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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