In other words, is there a relationship between the step size and the actual running time? Suppose that the algorithm is run on identical machine.

  • $\begingroup$ A real machine? That's a can of worms. $\endgroup$
    – Raphael
    Dec 16 '14 at 18:10
  • $\begingroup$ Let's suppose this machine is from the world of CLRS $\endgroup$
    – Fraïssé
    Dec 16 '14 at 18:11

There's no clear relationship, except that bigger inputs will tend to take longer. What we call the "running time" in complexity theory is the number of basic operations but we just choose some set of basic operations and assume that they all have the same cost. That's fine for asymptotic analysis but it doesn't correspond to the actual running time, as measured by a clock.

For example, imagine your algorithm consists of an initialization phase that takes one second, regardless of the input, plus a quadratic time loop that takes $n^2$ milliseconds to process $n$ items. Complexity theory just says that your algorithm has running time $\Theta(n^2)$, so doubling the size of the input multiplies the running time by four. Asymptotically, this is true but, if you double the input size from $10$ to $20$, the running time only changes from $1.1\,\mathrm{s}$ to $1.4\,\mathrm{s}$, which is nothing like a factor of four (it's less less than $30\%$).

Another problem is that complexity theory doesn't model the sheer... well, complexity of modern computers. A simple example: suppose your quadratic algorithm runs in half a second on an input of length $\ell$. Great, it's going to run in just over half a second on a similar input of length $\ell+1$, right? Maybe. Or maybe it takes ten seconds because your data doesn't fit in the cache any more.


The answer that your teacher or textbook expects is that doubling the input size doubles the running time. The implicit assumption is that the running time is exactly of the form $T(n) = Cn$. In that case, $T(2n) = C(2n) = 2(Cn) = 2T(n)$. In practice, $T(n) = \Theta(n)$ only implies that $cn \leq T(n) \leq Cn$. Therefore all we can say is that if $n$ is multiplied by some large $D$ then $$ D \frac{c}{C} T(n) \leq cDn \leq T(Dn) \leq CDn \leq D \frac{C}{c} T(n). $$ So for large enough $D$, multiplying $n$ by $D$ multiplies the running time by some factor lying in the interval $[(c/C)D,(C/c)D]$.

The simple interpretation is still helpful intuitively. Under this interpretation:

  • The running time is linear if doubling the input size doubles the running time.
  • The running time is poylnomial if doubling the input size multiplies the running time by a constant.
  • The running time is exponential if increasing the input size by a constant multiplies the running time by a constant.
  • The running time is logarithmic if doubling the input size increases the running time by a constant.
  • The running time is constant if it is independent of the input size.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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