We have looked at notions of computability, where there are no limits on home much time or memory a program can use.
For computability, the only requirement is that the program must eventually stop and produce an answer.
In complexity theory, we look at solving problems within given resource limitations.
For example, we might insist that a program use no more than a given amount of time.
The time limit is never a fixed number; that would be much too restrictive. Instead, we let n be the length of the input string, and express the limit as a function f(n). We say that a program runs within time f(n) if it makes no more that O(f(n)) steps on every input of length n.
For example, if f(n) = n2, the program is allowed to make O(n2) steps.
The other common resource is memory, also called space.
The most extreme space limit is finite state. There, a program must correctly solve arbitrarily large input without getting any more memory; the meory limit is O(1).
Less stringent memory limits are O(n) or O(n2).