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 fixedsize 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 builtin procedure car
. When car
is applied to a nonempty 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 builtin 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.

Since we are speculating based on what
car
does, not examining howcar
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 implementcar
in a way such that its running time that is not in $O(1)$. The implementation ofscar
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. ↩