Asymptotic worst case time and space complexity

Algorithm cost model

Definition. Complexity estimates resources as a function of input size n under a stated computational model. The RAM model treats basic arithmetic, comparison, assignment, and indexed access as constant-time operations when values fit a machine word. For bit complexity, the number of bits in values must also be counted.

Example. Scanning an n-element array performs n element inspections.

Exam point. State the input-size measure and cost model before deriving a bound.

Worst, average, and best case

Definition. Worst-case cost is the maximum over inputs of size n; best-case is the minimum. Average-case cost is an expectation under a specified probability distribution. A worst-case guarantee does not require assumptions about likely inputs.

Example. Linear search has best-case 1 comparison and worst-case n comparisons.

Exam point. “Average” is incomplete without an input distribution or randomization model.

Big-O notation

Definition. $f(n)=O(g(n))$ if there exist constants c>0 and n₀ such that $0\le f(n)\le c g(n)$ for all n≥n₀. It is an asymptotic upper bound and need not be tight. Constants and lower-order terms do not affect the classification for sufficiently large n.

Example. $3n^2+5n+7=O(n^2)$.

Exam point. O does not mean “exactly this growth rate.”

Solved check. Show that $4n+9=O(n)$ for n≥1.

1. For n≥1, $9\le9n$.
2. Then $4n+9\le13n$.
3. Choose c=13 and n₀=1. Answer. $4n+9=O(n)$.

Big-Omega notation

Definition. $f(n)=\Omega(g(n))$ if there exist constants c>0 and n₀ such that $f(n)\ge c g(n)$ for all n≥n₀. It is an asymptotic lower bound. A lower bound on an algorithm may refer to every input, an average input, or a worst-case input; the quantifier must be stated.

Example. $n^2+2n=\Omega(n^2)$ for n≥1.

Exam point. Do not confuse a lower bound on one input with a worst-case lower bound.

Big-Theta notation

Definition. $f(n)=\Theta(g(n))$ when f is both O(g) and Ω(g), for nonnegative functions eventually. It gives a tight asymptotic growth rate up to constant factors. Θ describes growth, not an exact operation count.

Example. $7n\log n+4n=\Theta(n\log n)$ for a fixed log base greater than 1.

Exam point. Prove both an upper and a lower bound for Θ.

Solved comparison. Classify $f(n)=2n^3+8n^2+100$ tightly.

1. Divide by the leading term scale n³: lower-order ratios are $8/n$ and $100/n³$.
2. They tend to zero as n grows.
3. For large n, f is bounded above and below by positive constant multiples of n³. Answer. $f(n)=\Theta(n^3)$.

Little-o and little-omega

Definition. $f(n)=o(g(n))$ means $f(n)/g(n)\to0$; $f(n)=\omega(g(n))$ means that ratio tends to infinity, for eventually positive g. These are strict asymptotic comparisons, unlike O and Ω, which allow constant factors. A function can be O(g) without being o(g).

Example. $n=o(n\log n)$ for n>1.

Exam point. Check the ratio limit to distinguish strict from non-strict bounds.

Comparing common growth rates

Definition. For fixed constants a>1 and k>0, logarithms grow more slowly than positive powers, and positive powers grow more slowly than exponentials. Factorials grow faster than fixed-base exponentials asymptotically. These orderings assume n tends to infinity and constant parameters do not vary with n.

Increasing growth (typical)	Class
$1$	constant
$\log n$	logarithmic
$n$	linear
$n\log n$	linearithmic
$n^2,n^3$	polynomial
$2^n$	exponential
$n!$	factorial

Example. For sufficiently large n, $n^2<2^n$.

Exam point. A higher polynomial degree eventually dominates any lower degree, regardless of fixed coefficients.

Solved ordering. Arrange $n,\log_2n,n^{1.5},n\log n$ by asymptotic growth.

1. $\log n=o(n)$.
2. $n=o(n\log n)$.
3. $n\log n=o(n^{1.5})$ because $\log n/\sqrt n\to0$. Answer. $\log n<n<n\log n<n^{1.5}$ asymptotically.

Simplifying sums and loops

Definition. A loop's cost is the sum of work over its iterations. A loop with n constant-work iterations costs Θ(n). Nested loops multiply iteration counts only when their ranges are independent; triangular bounds often give sums such as $1+2+\cdots+n=\Theta(n^2)$.

Example. for i=1..n, for j=1..n executes n² inner iterations.

Exam point. Derive bounds from the actual loop variables and update rules.

Solved count. Count executions of the body in for i=1..n: for j=1..i: work.

1. For i=1, body runs 1 time; for i=2, it runs 2 times.
2. Total is $\sum_{i=1}^{n}i=n(n+1)/2$.
3. Leading term is $n^2/2$. Answer. Θ(n²) executions.

Logarithmic loops

Definition. A loop that multiplies or divides a positive quantity by a fixed factor greater than 1 each iteration usually runs Θ(log n) times until it crosses a threshold. The logarithm base changes the count by a constant factor. The exact integer count depends on rounding and stopping condition.

Example. Repeatedly halve n until zero takes Θ(log n) iterations for positive n.

Exam point. Additive changes produce linear counts; multiplicative changes produce logarithmic counts.

Solved count. How many iterations does i=1; while(i<n) i*=3; execute for n=100?

1. Values at loop tests are 1,3,9,27,81.
2. Each is less than 100, so each causes an iteration.
3. The update makes i=243; the next test fails. Answer. 5 iterations; asymptotically Θ(log n).

Nested loops with changing bounds

Definition. When inner bounds depend on outer variables, count the sum rather than multiply maxima blindly. Geometric bounds may produce logarithmic or linear totals; triangular bounds often yield quadratic totals. Changing the increment can alter the sum substantially.

Example. If j doubles from 1 while j≤i, inner iterations are Θ(log i).

Exam point. Write the summation before simplifying the order.

Solved count. Count iterations of for i=1..n: for j=1; j<=n; j*=2.

1. The inner loop values are 1,2,4,...,2^k≤n.
2. Number of values is $\lfloor\log_2n\rfloor+1$.
3. This occurs for each of n outer iterations. Answer. $n(\lfloor\log_2n\rfloor+1)=\Theta(n\log n)$.

Space complexity

Definition. Auxiliary space counts extra working storage beyond the input when the convention says so; total space includes both. Recursion uses stack space proportional to maximum active depth and per-call frame size. In-place algorithms may still use recursion stack or fixed-size buffers.

Example. Iterative binary search uses O(1) auxiliary space; recursive binary search uses O(log n) stack space.

Exam point. State whether input storage is included.

Solved comparison. Merge sort on an array of n items and insertion sort on the same array: compare auxiliary space.

1. Standard array merge sort uses a temporary buffer proportional to n.
2. Insertion sort shifts items in the input array and uses a fixed number of temporaries.
3. Thus their auxiliary spaces differ even though both can sort in-place? Merge requires buffer under this implementation; in-place variants exist but use more complexity. Answer. Standard merge sort O(n) auxiliary space; insertion sort O(1).

Amortized analysis

Definition. Amortized cost bounds total cost over any sequence of operations, then divides by operation count; it does not assume random inputs. Aggregate, accounting, and potential methods can prove such bounds. A single operation may still be expensive even when amortized cost is small.

Example. Dynamic-array append with doubling is O(1) amortized though a resize costs O(n).

Exam point. Amortized analysis is a worst-sequence guarantee, not an average over a probability distribution.

Solved calculation. A dynamic array doubles capacity from 1. For n=8 appends, count element copies at resizes.

1. Resize before append 2 copies 1 element.
2. Resize before append 3 copies 2 elements.
3. Resize before append 5 copies 4 elements.
4. Total copies are 7, less than 8.
5. Over n appends, copied items form $1+2+4+\cdots<2n$. Answer. 7 copies for n=8; amortized append cost is O(1).