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
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.
eEL,CSA_Dept,IISc,Bangalore