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

$\ 
T(n) = 
\begin{cases}
  \theta(1) &amp; \text{if }n = 1\\    
  2T(\frac{n}{2}) + \theta(n) &amp; \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 &amp; \text{if }n = 1\\    
  2T(\frac{n}{2}) + cn &amp; \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 &amp; \text{if }n = 1\\    
  2T(\frac{n}{2}) + bn &amp; \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.
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.