7.4.1 No Growth: Constant Time

If the running time of a procedure does not increase when the size of the input increases, the procedure must be able to produce its output by looking at only a constant number of symbols in the input. Procedures whose running time does not increase with the size of the input are known as constant time procedures. Their running time is in $O(1)$ --- it does not grow at all. By convention, we use $O(1)$ instead of $\Theta(1)$ to describe constant time. Since there is no way to grow slower than not growing at all, $O(1)$ and $\Theta(1)$ are equivalent.

We cannot do much in constant time, since we cannot even examine the whole input. A constant time procedure must be able to produce its output by examining only a fixed-size part of the input. Recall that the input size measures the number of squares needed to represent the input. No matter how long the input is, a constant time procedure can look at no more than some fixed number of squares on the tape, so cannot even read the whole input.

An example of a constant time procedure is the built-in procedure car. When car is applied to a non-empty list, it evaluates to the first element of that list. No matter how long the input list is, all the car procedure needs to do is extract the first component of the list. So, the running time of car is in $O(1)$. 1 Other built-in procedures that involve lists and pairs that have running times in $O(1)$ include cons, cdr, null?, and pair?. None of these procedures need to examine more than the first pair of the list.

  1. Since we are speculating based on what car does, not examining how car a particular Scheme interpreter actually implements it, we cannot say definitively that its running time is in $O(1)$. It would be rather shocking, however, for an implementation to implement car in a way such that its running time that is not in $O(1)$. The implementation of scar in Section 5.2.1 is constant time: regardless of the input size, evaluating an application of it involves evaluating a single application expression, and then evaluating an if expression.