next up previous
Next: 1.2.5 Worst Case, Average Case, and Amortized Complexity Up: 1.2 Complexity of Algorithms Previous: 1.2.3 An Example: Complexity of Mergesort

1.2.4 Role of the Constant

The constant C that appears in the definition of the asymptotic upper bounds is very important. It depends on the algorithm, machine, compiler, etc. It is to be noted that the big "Oh" notation gives only asymptotic complexity. As such, a polynomial time algorithm with a large value of the constant may turn out to be much less efficient than an exponential time algorithm (with a small constant) for the range of interest of the input values. See Figure 1.1 and also Table 1.1.