09. Evaluating Algorithm Efficiency

Why Algorithm Efficiency Matters

Algorithm analysis estimates how an algorithm's resource requirements change as its input grows. Two algorithms may both produce correct answers while differing greatly in computational work or memory use.

The two principal resources are:

• Time complexity: the amount of computational work performed.

• Space complexity: the amount of memory required while the algorithm runs.

Analysis is usually more useful for comparing growth than timing one implementation on one computer, because measured time depends on hardware, programming language, compiler, and other system conditions. Efficiency is also different from Decidability: decidability asks whether a problem can be solved algorithmically at all, whereas efficiency asks how many resources a solving algorithm requires.

Takeaway: Begin by asking how time and memory change as the input becomes larger, not merely how fast one particular run appears.

Modeling Input Size and Basic Operations

Before counting operations, define the input-size variable and select a simplified cost model. Let $n$ represent the relevant measure of input size. For example, $n$ may be the number of elements in an array, the number of records being sorted, or the number of bits in a binary representation.

A cost model specifies which operations count as basic operations. Assignments, arithmetic operations, comparisons, array accesses, and Boolean tests are often treated as constant-time operations. If an algorithm performs $T(n)$ basic operations on an input of size $n$, then $T(n)$ is its operation-count function.

For a loop that initializes a sum and then adds one value for each of $n$ input positions, the loop body executes $n$ times. A simple count might be written as

The constants depend on what the model counts, but the important fact is that the work grows linearly with $n$. A fixed statement such as one arithmetic assignment contributes $O(1)$, because its work does not grow with $n$.

Takeaway: A meaningful efficiency analysis states what $n$ measures and what operation is being counted.

Counting Work from Program Structure

The structure of an algorithm determines how operation counts combine.

• A fixed amount of work contributes $O(1)$.

• Consecutive sections are added. Two linear sections give $O(n) + O(n) = O(2n)$, which simplifies to $O(n)$.

• For an if-else statement, a worst-case upper-bound analysis uses the more expensive branch.

• Nested loops often multiply iteration counts.

• Repeatedly halving the remaining work produces logarithmic growth.

For nested loops that each run $n$ times, the inner operation executes $n \times n = n^2$ times, giving $O(n^2)$. If the inner loop runs from $1$ through the current outer-loop value, the count is

which still grows as $n^2$. By contrast, a loop that repeatedly replaces its remaining value by $\lfloor n/2 \rfloor$ runs for approximately $\log_2 n$ iterations. This is the pattern used by binary search, where each comparison eliminates about half of the remaining candidates in a sorted array.

Takeaway: Add sequential work, multiply independent nested work, and look for repeated halving when identifying logarithmic behavior.

Best, Worst, and Average Cases

The same input size can produce different amounts of work depending on the arrangement or values of the input. Analysis therefore distinguishes among cases:

• Best case: the least work required for an input of size $n$.

• Worst case: the greatest work required for an input of size $n$.

• Average case: the expected work under an assumed distribution of inputs.

A linear search illustrates the distinction. If the target is the first element, the best-case time is $O(1)$. If the target is last or absent, the worst-case time is $O(n)$. Under common assumptions, the average search examines approximately $n/2$ elements, which is still $O(n)$.

The notation $O(f(n))$ describes a growth upper bound; it does not automatically mean worst case. A complete statement identifies both the bound and the case, such as “the worst-case time is $O(n)$.”

Takeaway: Always state which input behavior is being analyzed before interpreting a complexity result.

Growth Rates and Asymptotic Comparison

Asymptotic analysis compares growth for sufficiently large inputs while ignoring constant factors and lower-order terms. This approach is summarized by asymptotic notation.

For example,

has quadratic growth because the $n^2$ term eventually dominates the linear and constant terms. Common growth rates, ordered from generally more scalable to less scalable, include:

• $O(1)$: constant, such as accessing an array element by index.

• $O(\log n)$: logarithmic, such as binary search.

• $O(n)$: linear, such as scanning every element once.

• $O(n \log n)$: linearithmic, such as efficient comparison-based sorting.

• $O(n^2)$: quadratic, such as comparing every pair of elements.

• $O(n^3)$: cubic, such as three nested loops over $n$ items.

• $O(2^n)$: exponential, such as many exhaustive recursive searches.

• $O(n!)$: factorial, such as trying every permutation.

Doubling $n$ approximately doubles linear work but can quadruple quadratic work. Thus, a method that works for small inputs may become impractical as the input grows.

Takeaway: The dominant growth term is usually the most important predictor of scalability.

Upper, Lower, and Tight Bounds

The three principal bound notations describe different relationships between an operation-count function and a comparison function.

Big-O notation is an upper bound. Writing

means there are positive constants $c$ and $n_0$ such that

for every $n \geq n_0$. For example, $3n^2 + 2n + 5 \in O(n^2)$. It is also technically in $O(n^3)$, but the quadratic bound is tighter and more informative.

Big-Ω notation is a lower bound. Writing

means that, for sufficiently large $n$, the algorithm's work is at least a constant multiple of $f(n)$.

Big-Θ notation is a tight bound. It means both an upper and a lower bound hold:

Therefore,

Takeaway: Big-O limits growth from above, Big-Ω limits it from below, and Big-Θ captures the exact asymptotic growth class.

Time and Space as Separate Resources

Space complexity measures memory use as a function of input size. Separate the memory needed to store the original input from the additional memory created during execution.

• Input space is the memory needed to store the original input.

• Auxiliary space is the additional memory used by the algorithm beyond that input.

An algorithm that scans an input array, keeps a running sum, and uses only a fixed number of additional variables has $O(1)$ auxiliary space, even though the input array contains $n$ values.

By contrast, an algorithm that creates a new array of length $n$ and copies every element into it uses $O(n)$ auxiliary space. Algorithms may trade time for space: storing previously computed results can reduce repeated computation while increasing memory use.

Takeaway: Analyze additional storage separately from the input and report its growth as a function of $n$.

A Repeatable Analysis Workflow

Use the following sequence to analyze an unfamiliar algorithm:

1. Define the input size. State exactly what $n$ measures.

2. Choose the basic operation. Select the repeated operation that best represents the work.

3. Count executions. Determine how often that operation occurs.

4. Write the operation-count function. Express the result as $T(n)$.

5. Simplify asymptotically. Remove constant factors and lower-order terms.

6. State the case or bound. Identify whether the result is best-case, worst-case, average-case, or a bound applying to all inputs.

7. Analyze memory separately. Count additional storage as a function of $n$.

Consider a duplicate-finding algorithm that compares every pair of array elements. In the worst case, no duplicate is found, so all pairs are examined. The number of comparisons is

The dominant term is quadratic, so the worst-case time complexity is $\Theta(n^2)$. Only a fixed number of index variables is used, so the auxiliary space complexity is $\Theta(1)$.

A complete analysis connects a precise count to a case, a simplified bound, and a separate memory calculation. Big-O analysis is a model rather than a stopwatch measurement: it does not normally provide exact running time in seconds or capture every constant caused by hardware, implementation, caching, input/output, or parallel execution. For small inputs, an algorithm with a higher asymptotic growth rate can sometimes be faster because constants and lower-order terms matter. As inputs grow, the lower growth rate generally becomes increasingly important.

Takeaway: Use asymptotic analysis to reason about scalability, while keeping its assumptions and limits in view.