We are considering computational problems with input size proportion to a variable n. Sometimes we are interested in worst-case time performance, and sometime in average-case time performance. We may also sometimes be interested in the amount of space (memory) a problem requires. Mostly we will be interested in upper bounds for the performance, and often tight upper bounds if we can obtain them. Lower bounds are also of great interest, but it is usually not possible to prove such bounds. We are rarely interested in best-case performance.

Keep in mind that a given problem may have a number of algorithms that solve it, with differing performance. Thus we can talk about the difficulty of an algorithm, or the inherent difficulty of a problem, that is, what is the best you can do on the problem with any algorithm.

Here are some big-O or big-Θ bounds, with a corresponding algorithm afterwards:

• O(1). Constant time. (Hash-table look-up.)

• O(log(log(n))). (Interpolation search.)

• O(log(n)). (Binary search.)

• O(√n). (Simplest prime testing algorithm.)

• O(n). (Linear search.)

• O(n*log(n)). (High performance sorts.)

• O(n²). (Low-performance sorts. Matrix addition.)

• O(n³). (Ordinary matrix multiplication.)

• O(n⁸). (Artificial problems.

• O(n^k), for some fixed k. This is the class P of polynomial-time algorithms.

• The class NP of problems. These might all be in P, but likely not, though nobody knows.

• The class NP-Complete of problems. These are the hardest problems in NP. These might also be in P, but likely not, though nobody knows. This is a large class of optimization problems that are important in many areas. This has been an extremely active area of study since 1970.

• O(2ⁿ). Problems which require exponential time.

• O(2^{22 ...2n)}. Believe it or not, there are problems that can be solved, but which require more than this amount of time for any finite number of 2s. An example is the problem of deciding whether or not an extended regular expression defines the empty set.

• Undecidable problems. Also called unsolvable problems. These are problems that cannot be solved by any algorithm or machine or model of computation known to humans. An example is the Halting Problem: it is impossible to decide in general whether a given computer program with a given input will execute forever or will eventually halt.