# 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) & \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.

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