Complexity, Asymptotic Bounds and Recurrences

1. Measuring Resource Growth

Algorithm analysis studies how required resources grow with input size. Time complexity counts selected elementary operations, while space complexity measures storage used during execution.

Instead of timing one program on one machine, analysis builds a mathematical cost function such as:

T(n) = 3n² + 7n + 12

This function shows how work changes as n grows. Actual time still depends on implementation, language, hardware, cache, input distribution and constants.

2. Defining Input Size

The symbol n must have a stated meaning. It may be:

• number of array elements;
• number of digits or bits in an integer;
• number of vertices and edges in a graph;
• number of records and key length;
• rows and columns of a matrix.

Graph complexity often uses V and E because a graph with the same number of vertices can have very different edge counts.

For arbitrary-size arithmetic, adding two n-bit numbers is not constant time. The unit-cost model for fixed-width machine integers must be stated.

3. A Cost Model

A cost model decides which operations count as constant. Array indexing, comparison and fixed-width arithmetic are often treated as O(1) in the RAM model.

String comparison can depend on string length. Copying an object can depend on its stored data. Hashing a key can depend on key length.

Analysis should expose costs that grow with the input rather than hide them inside a method name.

4. Best, Worst and Average Cases

For input size n:

• best case is the minimum cost among accepted inputs;
• worst case is the maximum;
• average case is expected cost under a stated probability distribution.

Linear search has best-case Θ(1) when the first element matches and worst-case Θ(n) when the target is last or absent.

Average case is meaningless without a model. Assuming every target position is equally likely differs from including unsuccessful searches or skewed access.

5. Big O

f(n) is O(g(n)) when there are positive constants c and n₀ such that:

0 <= f(n) <= c g(n) for all n >= n₀

Big O is an asymptotic upper bound. It does not itself mean worst case. First define the cost function, such as worst-case time; then Big O can bound that function.

3n + 5 is O(n), O(n²) and O(2ⁿ). O(n) is the most informative among these common upper bounds because it is tight.

6. Big Omega

f(n) is Ω(g(n)) when positive c and n₀ exist such that:

0 <= c g(n) <= f(n) for all n >= n₀

Omega is an asymptotic lower bound. It describes growth that f cannot fall below beyond a threshold.

Every comparison-based sort needs Ω(n log n) comparisons in the worst case under the decision-tree model, while a particular inefficient sort may take more.

7. Big Theta

f(n) is Θ(g(n)) when it is both O(g(n)) and Ω(g(n)). Theta is a tight asymptotic bound:

c₁ g(n) <= f(n) <= c₂ g(n)

for sufficiently large n.

If T(n) = 3n² + 7n + 12, then T(n) is Θ(n²). The lower-order terms and positive constant multiplier do not change its asymptotic growth class.

Use Theta when both upper and lower growth are known.

8. Little-o and Little-omega

Little-o expresses a strict upper growth relation. f(n) is o(g(n)) when f(n)/g(n) approaches zero. Thus n is o(n log n).

Little-omega expresses a strict lower relation. n² is ω(n log n).

These notations distinguish “grows no faster than” from “grows strictly more slowly.” They appear more often in formal analysis than everyday implementation discussion.

9. Growth Classes

Common increasing growth rates are:

Θ(1)
Θ(log n)
Θ(n)
Θ(n log n)
Θ(n²)
Θ(n³)
Θ(cⁿ), c > 1
Θ(n!)

For sufficiently large n, exponential growth exceeds every fixed-degree polynomial. n² grows faster than n log n.

Growth class is not the only engineering concern. For realistic small n, a simple quadratic algorithm with small constants can beat a complex n log n algorithm.

10. Sequential Statements

Sequential costs add:

loop n times
loop n times

gives:

an + bn + c = Θ(n)

Do not multiply because the second loop does not run inside the first.

For phases with different growth, the dominant term controls the sum:

Θ(n²) + Θ(n) = Θ(n²)

Both phases may still matter for actual optimization.

11. Nested Loops

Independent nested loops multiply:

for i = 0 to n-1
    for j = 0 to n-1
        constant work

The inner work runs n times for each of n outer iterations, giving n² total operations and Θ(n²).

If dimensions differ, preserve them:

for each of r rows
    for each of c columns

costs Θ(rc), not automatically Θ(n²).

12. Dependent Loop Bounds

For:

for i = 1 to n
    for j = 1 to i
        constant work

the total is:

1 + 2 + ... + n = n(n + 1)/2 = Θ(n²)

Do not multiply maximum loop bounds blindly. Sum the actual inner iterations.

A triangular loop remains quadratic because roughly half of an n by n grid is still proportional to n².

13. Logarithmic Loops

Repeated multiplication or division gives logarithmic iterations:

i = 1
while i < n
    i = i * 2

After k iterations, i = 2ᵏ. The loop stops around k = log₂ n, so cost is Θ(log n).

Changing logarithm base changes only a constant factor:

log_a n = log_b n / log_b a

Thus asymptotic notation normally writes log n without a base.

14. Mixed Loops

A linear outer loop containing a logarithmic inner loop costs Θ(n log n):

for each element
    repeatedly halve a search interval

But verify that the logarithmic work truly repeats independently for every element. If a pointer advances globally and never moves backward, two syntactically nested loops may together be linear.

Analysis follows total state changes, not indentation alone.

15. Conditionals

For worst-case analysis of:

if condition
    operation A
else
    operation B

use the more expensive possible branch:

Θ(max(cost(A), cost(B)))

For expected cost, branch probabilities are needed. A condition that exits early can produce different best and worst cases, as in linear search.

16. Space Complexity

Total space can include input, output and working storage. Auxiliary space ordinarily excludes input storage and focuses on extra memory used by the algorithm.

An in-place array reversal uses Θ(1) auxiliary space. Merge sort on arrays commonly uses Θ(n) auxiliary storage. An adjacency matrix uses Θ(V²) representation space, while an adjacency list uses Θ(V + E).

State what is included. Output-sensitive algorithms may necessarily allocate space proportional to the output.

17. Recursion Stack Space

Each active recursive call has an activation record containing parameters, local variables, return information and saved state.

Stack usage depends on maximum simultaneous call depth times relevant frame size, not total calls over the entire execution.

Recursive factorial has depth Θ(n), so it uses Θ(n) stack space. A balanced binary recursion may make many total calls but have only Θ(log n) depth.

Java does not guarantee general tail-call elimination, so tail recursion still consumes stack frames.

18. Recurrences

A recurrence expresses recursive cost. Binary search gives:

T(n) = T(n/2) + Θ(1)

Merge sort gives:

T(n) = 2T(n/2) + Θ(n)

A recurrence needs a base case such as T(1) = Θ(1). Solve it by expansion, a recursion tree, substitution or the Master theorem when applicable.

19. Expansion

For:

T(n) = T(n/2) + c

expand:

T(n) = T(n/4) + 2c
     = T(n/8) + 3c

After k levels, the subproblem has size n/2ᵏ. It reaches 1 when k = log₂ n. Total work is Θ(log n).

For:

T(n) = T(n - 1) + Θ(1)

there are n levels, giving Θ(n).

20. Recursion Trees

For merge sort:

T(n) = 2T(n/2) + cn

At level 0, nonrecursive work is cn. At level 1, two nodes each do c(n/2), totaling cn. Every level totals Θ(n).

The tree has Θ(log n) levels, so total cost is Θ(n log n).

Leaves contribute Θ(n) additional work, which does not change the tight bound.

21. Master Theorem

For recurrences:

T(n) = aT(n/b) + f(n)

compare f(n) with n^(log_b a).

• If f is polynomially smaller, recursive leaves dominate.
• If f has the same order with compatible logarithmic factors, levels balance.
• If f is polynomially larger and a regularity condition holds, root-side work dominates.

Examples:

2T(n/2) + Θ(1) = Θ(n)
2T(n/2) + Θ(n) = Θ(n log n)
2T(n/2) + Θ(n²) = Θ(n²)

The theorem does not apply directly to every recurrence, including many unequal or n - 1 subproblems.

22. Amortized Analysis

Amortized analysis bounds total cost across any relevant operation sequence and divides it among operations. It does not assume a random input distribution.

A dynamic array doubles capacity when full. One growth append can allocate and copy Θ(n) elements, but many intervening appends cost Θ(1).

Across n appends, copied elements form a geometric sum:

1 + 2 + 4 + ... < 2n

Total append work is Θ(n), so amortized cost per append is Θ(1).

23. Aggregate, Accounting and Potential Methods

The aggregate method directly bounds the total cost of n operations.

The accounting method charges inexpensive operations extra credit that pays for a later expensive one.

The potential method defines stored potential Φ(state). Amortized cost is:

actual cost + Φ(after) - Φ(before)

All three methods establish a sequence guarantee. They are not the same as average-case probability analysis.

24. Output-Sensitive Complexity

Some problems necessarily spend time proportional to result size. Reporting k matches may cost:

O(search cost + k)

A graph traversal that prints every reachable vertex needs at least Ω(number printed).

Output-sensitive notation separates the cost of finding results from the unavoidable cost of producing them.

25. Representation-Sensitive Complexity

BFS with an adjacency list takes Θ(V + E) because it scans each vertex and stored edge. With an adjacency matrix, it inspects a full row of V possible neighbors for each visited vertex, giving Θ(V²).

The algorithm name alone is not a complete complexity claim. State representation, operations and input parameters.

Hash-table lookup is expected O(1) under hashing assumptions but can be O(n) in the worst case. Tree search depends on height.

26. Practical Performance

Asymptotic analysis ignores constants and lower-order terms to describe scaling. Real performance also depends on:

• cache locality;
• allocation;
• branch prediction;
• virtual dispatch;
• interpreter or JIT behavior;
• data distribution;
• parallelism;
• I/O and network delays.

Use analysis to eliminate designs that scale poorly, then benchmark correct implementations with representative workloads. Measurements without analysis can overfit one dataset; analysis without measurement can miss dominant engineering costs.

27. A Reliable Analysis Method

1. Define input-size variables.
2. State the cost model.
3. Choose best, worst, expected or amortized case.
4. Count loop iterations or derive a recurrence.
5. Include hidden costs such as copying or key comparison.
6. Calculate auxiliary and recursion space separately.
7. simplify to a tight asymptotic bound where possible.
8. state representation and assumptions.

A complexity statement is useful only when its input measure, case, model and bound are clear.