Asymptotic bounds and recurrence solving

For eventually nonnegative functions, f belongs to O(g) when one positive constant times g bounds f above for every sufficiently large input size. Omega reverses the inequality; Theta requires both directions. A quadratic function is also O(n cubed), so an upper bound alone need not identify its growth rate tightly. The constants and starting threshold may depend on a fixed algorithm, but not on the growing size n. Small benchmark differences do not contradict an eventual bound.

Define the cost function before bounding it. Worst-case time at size n maximizes over all permitted inputs of that size. Best-case time minimizes instead; expected time requires a stated probability space. An array scan can be constant-time on its best input and linear-time in its worst case. The word average is incomplete without saying whether inputs are sampled or the algorithm itself tosses coins. Space bounds likewise distinguish input storage, auxiliary storage, and recursion-stack depth.

Suppose a procedure removes one item and then performs work equal to the current size. With base cost T(1) = 1 and recurrence T(n) = T(n−1) + n for integers n at least two, repeated expansion sums the integers from one through n. Pairing the first and last terms gives the familiar triangular number. The result is Theta(n squared), because its ratio to n squared stays between two positive constants for all positive n.

An induction is short but still useful. Substitute the proposed expression for T(n−1), add n, and simplify to the expression at n. Check n = 1 separately. For inequalities, choose constants large enough to absorb base costs and lower-order terms rather than pretending an asymptotic expression is an exact equation. A common mistake is to use the desired bound in an inductive hypothesis too weak to close the next step; strengthening the hypothesis can repair the proof.

In a word-RAM analysis, operations on words of logarithmic size in the problem dimensions are usually charged constant time within the declared instruction set. Arbitrarily large integers do not fit that assumption. Adding two b-bit integers by the ordinary digitwise method takes O(b) bit operations. A recurrence counting one addition per stage can therefore understate the bit cost when intermediate values grow. Resource analyses are model-relative statements, not properties of source-code line counts alone.

Encoding also changes what polynomial means. A positive integer N written in binary needs roughly log base two of N bits. Performing N iterations is linear in its numeric value but exponential in its bit length on some inputs. Such a running time is called pseudopolynomial when polynomial dependence on numeric magnitudes replaces polynomial dependence on their encoded lengths. This distinction later prevents a knapsack table indexed by capacity from becoming an accidental proof that an NP-complete decision problem has a polynomial-time algorithm.