07 — Efficiency and Computational Complexity

07 — Measuring time and space

An algorithm is a precisely specified procedure that produces a result from an input. Two algorithms may solve the same problem correctly while requiring different amounts of time or memory.

Let $n$ denote the input size. For an array, $n$ may be the number of elements; for a graph, relevant measures may include the number of vertices $|V|$ and edges $|E|$.

Time complexity measures how computational work grows with $n$. Space complexity measures how memory requirements grow with $n$. Exact elapsed time depends on hardware, language, implementation, and input details, so complexity analysis focuses on the growth pattern rather than a particular number of seconds.

For space complexity, distinguish among:

• Input space: memory needed to store the input.

• Auxiliary space: additional memory used by the algorithm.

• Output space: memory needed to store the result.

A scan that finds the maximum element in an array uses $\Theta(1)$ auxiliary space, while copying the array into a second array uses $\Theta(n)$ additional space.

Takeaway: Define the input size and the resource being measured before assigning a complexity.

Growth rates and common complexity classes

The growth rate of an algorithm is often more informative for large inputs than a particular count of seconds. Common classes include:

• Constant: $\Theta(1)$, such as accessing an array element by index.

• Logarithmic: $\Theta(\log n)$, such as binary search on sorted data.

• Linear: $\Theta(n)$, such as scanning an array.

• Linearithmic: $\Theta(n\log n)$, such as merge sort.

• Quadratic: $\Theta(n^2)$, such as comparing every pair of elements.

• Polynomial: $\Theta(n^k)$ for a fixed $k$, such as a fixed number of nested loops.

• Exponential: $\Theta(2^n)$, such as trying every subset of an $n$-element set.

A linear search may inspect every element, giving a worst-case bound of $O(n)$. Binary search repeatedly halves the remaining interval, giving $O(\log n)$, but it requires the array to be sorted.

For sufficiently large inputs, constant factors and lower-order terms usually matter less than the growth class. Thus, $100n$ and $n$ have the same asymptotic class, while $n^2$ eventually grows faster than either linear function.

Takeaway: A faster-growing class can become impractical even when its initial constants are small.

Asymptotic bounds and input cases

Asymptotic notation describes growth for sufficiently large inputs. Big-O is an upper bound, Big-Omega is a lower bound, and Big-Theta is a tight bound.

For a function $f(n)$ and comparison function $g(n)$:

• $f(n)=O(g(n))$ means that $f(n)$ eventually grows no faster than a constant multiple of $g(n)$.

• $f(n)=\Omega(g(n))$ means that $f(n)$ eventually grows at least as quickly as a constant multiple of $g(n)$.

• $f(n)=\Theta(g(n))$ means both bounds hold.

For example:

The notation does not itself specify a best case, average case, or worst case. Those labels describe the inputs or probability distribution under consideration, whereas $O$, $\Omega$, and $\Theta$ describe mathematical bounds.

Takeaway: Always state both the asymptotic bound and the case being analyzed.

Reading complexity from code

Code structure often reveals the dominant growth rate.

Sequential parts add. If one section takes $\Theta(n)$ time and the next takes $\Theta(n^2)$ time, then:

The fastest-growing term dominates.

Nested loops usually multiply. If each of two loops runs $n$ times and the inner operation takes constant time, the total work is:

A loop that repeatedly halves a value has a logarithmic iteration count. For example, a loop that continues while $n>1$ and replaces $n$ with $\lfloor n/2\rfloor$ takes $\Theta(\log n)$ iterations.

Recursion requires a recurrence. Merge sort divides the input into two halves, recursively sorts both, and merges in linear time:

This gives:

Its standard merging process also uses $\Theta(n)$ auxiliary space.

Takeaway: Count repetitions, identify dominant terms, and write a recurrence when recursive calls determine the work.

Time–space trade-offs and practical analysis

Algorithm selection depends on workload and constraints, not only on one asymptotic number. Repeated membership queries illustrate the choices:

• Scanning an unsorted array takes $O(n)$ time per query and uses little extra space.

• Sorting first adds preprocessing cost, after which binary search takes $O(\log n)$ per query.

• A hash table may use $O(n)$ extra space and provide expected $O(1)$ lookup time.

For one query, preprocessing may not be worthwhile. For many queries, preprocessing can reduce total time. A memory-constrained device may favor the lower-space method, while a system requiring predictable worst-case performance may favor a balanced search tree instead of a hash table.

Other choices include storing precomputed results instead of recomputing them, caching frequently used data, accepting slower but simpler code, and spending more resources for greater numerical accuracy. Constants, actual input sizes, hardware, implementation quality, memory limits, and input distributions can all affect practical performance.

A practical procedure is:

1. Define what $n$ measures.

2. Choose the resource: time, auxiliary space, or both.

3. Count dominant operations such as comparisons, iterations, calls, or data movements.

4. State whether the analysis is best-case, average-case, or worst-case.

5. Remove constant factors and lower-order terms.

6. Check assumptions such as sorted data, expected hashing behavior, and the computational model.

7. Compare trade-offs involving preprocessing, memory, predictability, simplicity, and workload.

Takeaway: Choose an algorithm by matching its resource behavior and assumptions to the task it must perform.

• time–space trade-off