Complexity

Suppose a program must answer many exact-name queries over the same array. An unsuccessful scan can inspect all n names, so q queries can perform qn comparisons. Sorting once takes roughly n log_2 n comparisons, after which each binary search needs roughly log_2 n, for a combined scale of n log_2 n + q log_2 n. For one query, sorting first is more expensive than scanning; preprocessing pays off only when enough later queries reuse the sorted order.

Complexity analysis predicts how resource use grows with input size independently of one machine or benchmark. It provides the vocabulary to compare algorithms, expose scalability limits, and identify the assumptions behind those comparisons.

The query example also shows why a bound must describe the whole workload. Ignoring constant factors, sorting becomes preferable when

Solving for q gives

which approaches log_2 n as n grows. This is not an exact deployment threshold—comparison cost, cache behavior, mutation, and the cost of preserving a sorted copy matter—but it derives a useful first estimate. The analysis changes immediately if insertions occur between queries or if a hash table can provide expected constant-time lookup.

Input Size

Complexity is always a function of a declared input-size measure. For an array, n is normally its element count. For a graph, two parameters—V vertices and E edges—usually describe the work more honestly than one. For an r x c matrix, size may be the pair (r,c) or the total cells rc. A positive integer x encoded in binary occupies floor(log_2 x) + 1 bits, not x bits.

This distinction explains pseudo-polynomial bounds. A subset-sum algorithm performing work proportional to nT is polynomial in numeric target T but can be exponential in the number of bits needed to write an unrestricted T. Measure the representation that reaches the program, not only the numeric value it denotes.

Output size can impose a lower bound. Printing all n! permutations must write n * n! elements. No internal optimization can produce that output in fewer than a proportional number of writes.

Cost Models

A cost model says which primitive operations count as constant time. The common word-RAM model assigns constant cost to arithmetic, comparison, assignment, and memory access on fixed-width machine words. It is appropriate only while values and addresses fit those words.

Other models answer other questions:

• the comparison model charges for comparisons and underlies sorting lower bounds;
• a bit-complexity model charges according to operand length, so multiplying thousand-bit integers is not one step;
• an I/O model counts transfers between memory levels, crucial for external sorting and databases;
• a parallel model separates total work from critical-path depth.

A bound without its model can be misleading. Hash lookup has expected constant cost only under assumptions about hashing and collision behavior; arithmetic on an arbitrary-precision number is not constant merely because it appears in one source-level expression.

Timing Limits

Benchmarks measure observed running time, but they do not replace complexity analysis for three reasons:

1. Hardware varies. The same program can take different times on a laptop, server, or phone. Wall-clock time measures the platform as well as the algorithm.
2. Implementations vary. Compiler options, memory layout, caching, and implementation quality can outweigh asymptotic differences on small inputs.
3. Measurements have limited scope. A measurement at one input size does not by itself predict behavior at a much larger size or under a different input distribution.

Asymptotic analysis describes how the amount of work grows with input size while suppressing platform-specific constants. A benchmark and an asymptotic bound answer different questions: “four seconds” describes one measured run, while “quadratic growth” predicts that multiplying n by ten multiplies dominant work by about one hundred.

Operation Counts

Instead of measuring time, we count elementary operations — comparisons, assignments, arithmetic operations, array accesses — as a function of the input size, conventionally written n. We don’t care about the exact count (that depends on the machine and the compiler); we care about how the count grows as n grows.

Consider this function, which finds the largest value in an array of n integers. Its contract requires n > 0 and a non-null pointer to at least n readable integers:

int find_max(int items[], int n) {
    int largest = items[0];            /* one initialization */
    for (int i = 1; i < n; i++) {      /* n - 1 iterations */
        if (items[i] > largest) {       /* one comparison per iteration */
            largest = items[i];         /* at most one assignment per iteration */
        }
    }
    return largest;
}

If the array has n items, this function performs roughly 1 + (n - 1) + (n - 1) operations in the worst case — call it 2n - 1. Now compare it to a function that checks whether an array contains any duplicate values by comparing every pair:

#include <stdbool.h>

bool has_duplicate(const int items[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (items[i] == items[j]) {
                return true;
            }
        }
    }
    return false;
}

Here, the inner loop runs $n - 1$, then $n - 2$, then $n - 3$ times, and so on, for a total of roughly $\frac{n(n-1)}{2}$ comparisons — about $n^2/2$.

Look at how differently these two expressions behave as n grows:

At n = 10, the counts are close enough that constants may dominate measured time. At n = 1,000,000, the estimates are about two million and five hundred billion operations. Asymptotic notation captures the linear-versus-quadratic growth that creates this widening gap.

Asymptotic Notation

Big O

Big-O notation describes an upper bound on how an algorithm’s running time grows. Formally:

A function $f(n)$ is $O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $f(n) \leq c \cdot g(n) \quad \text{for all } n \geq n_0$

In plain language, after some threshold, $f$ grows no faster than a constant multiple of $g$. Thus $2n - 1$ and $500n + 3$ are both $O(n)$, while $n^2/2$ is not $O(n)$.

Examples:

• $f(n) = 3n + 7$ is $O(n)$. Choose $c = 10$ and $n_0 = 1$: for any $n \geq 1$, $3n + 7 \leq 10n$.
• $f(n) = n^2 + 2n + 1$ is $O(n^2)$. Choose $c = 4$ and $n_0 = 1$: for $n \geq 1$, $n^2 + 2n + 1 \leq 4n^2$.
• $f(n) = n^2 + 2n + 1$ is also $O(n^3)$, $O(n^{100})$, and $O(2^n)$. Because Big-O is an upper bound, a looser upper bound may remain true; the tight bound is more informative.

For f(n) = 100, choosing c = 100 and n_0 = 1 proves f(n) = O(1). For f(n) = log_2 n + 5, choosing c = 6 and n_0 = 2 proves f(n) = O(log n) because log_2 n >= 1 on that range.

Omega and Theta

Big-O bounds a function from above. Two companion notations complete the standard vocabulary:

• Big-Omega (Ω) bounds growth from below: f(n) is Ω(g(n)) if f eventually grows at least as fast as a positive constant multiple of g.
• Big-Theta (Θ) is a tight bound: f(n) is Θ(g(n)) if it is both O(g(n)) and Ω(g(n)) — that is, f and g grow at exactly the same rate, up to constants.

For find_max, the function always performs roughly 2n - 1 operations regardless of the input’s contents, so its running time is Θ(n)—a tight characterization. For binary search, the best case (Theta(1), the midpoint matches) and worst case (Theta(log n)) differ, so each case must be stated separately.

Case analysis and asymptotic notation are independent dimensions. For example, an algorithm’s worst-case running-time function can have both an upper and a lower bound. When a tight bound is known, Theta states it precisely.

Growth Rates

The following common growth rates are ordered from slower to faster growth:

The jump from polynomial growth (n, n², n³, …) to exponential growth (2ⁿ, n!) is decisive. An algorithm that takes n² microseconds on an input of size 50 finishes in 2.5 milliseconds. An algorithm that takes 2ⁿ microseconds on the same input takes about 35 years. Complexity theory uses this gap when distinguishing polynomial-time tractability from exponential exact search.

Vary the input size below to compare how the major growth classes separate numerically:

An O(n²) algorithm with small constants can outperform an O(n log n) algorithm with larger overhead on small inputs. Production sorting libraries therefore switch to insertion sort for small subarrays. Asymptotic analysis describes long-run growth; benchmarks describe a particular implementation, platform, and workload. Both are needed for an engineering choice.

Space Complexity

Time complexity counts growing work; space complexity counts growing storage. State whether a bound includes the input itself or only auxiliary space allocated by the algorithm.

find_max stores one extra scalar regardless of n, so it uses O(1) auxiliary space. A function that creates a length-n output array uses O(n) output storage. Recursion also consumes space: if n calls remain active simultaneously, their stack frames require O(n) auxiliary space even without malloc. Excessive depth can exhaust the finite C call stack.

Time and space can be traded. Memoization stores solved states to avoid repeated computation, indexes spend preprocessing space to accelerate queries, and in-place methods save memory at possible cost to simplicity, stability, or running-time guarantees.

Analysis Toolkit

You rarely need to invoke the formal definition of Big-O directly. Instead, you build up an estimate by composing a small number of rules:

1. Sequential statements add (and the largest term wins). If a block of code does something that’s O(f(n)) followed by something that’s O(g(n)), the whole block is O(f(n) + g(n)), which simplifies to O(max(f(n), g(n))). Doing one O(n) pass and then one O(n²) pass is O(n²) overall — the linear pass is asymptotically irrelevant.

2. Loops multiply. A loop that runs k times, each iteration doing O(f(n)) work, costs O(k · f(n)). This is why a single loop over the input is O(n), and why nested loops — a loop inside a loop, each running roughly n times — give you O(n · n) = O(n²).

3. Conditionals take the worst branch. An if/else where one branch costs O(f(n)) and the other O(g(n)) costs O(max(f(n), g(n))) in the worst case — but remember that the best case might take the cheaper branch, which is why best-case and worst-case analyses can diverge.

4. Function calls cost what the function costs. If you call a function that’s O(f(n)) inside a loop that runs O(k) times, the total is O(k · f(n)). This rule trips people up constantly: a single linear scan tucked inside a loop — “is this value already in the array I’ve collected so far?” — can silently turn an O(n) algorithm into an O(n²) one.

5. Recursive calls require a recurrence. Express the cost in terms of smaller instances, including both the number and sizes of recursive calls and the nonrecursive work. The Recursive Design chapter develops methods for solving these recurrences.

Dominant Cost

#include <stdbool.h>

typedef struct {
    double value;
    int category;
} Record;

void summarize(Record records[], int n, double *out_total,
    int unique_categories[], int *out_unique_count) {
    double total = 0.0;
    for (int i = 0; i < n; i++) {            /* O(n) */
        total += records[i].value;
    }

    int unique_count = 0;
    for (int i = 0; i < n; i++) {            /* O(n) outer loop... */
        bool seen = false;
        for (int j = 0; j < unique_count; j++) {  /* ...times an O(k) scan */
            if (unique_categories[j] == records[i].category) {
                seen = true;
                break;
            }
        }
        if (!seen) {
            unique_categories[unique_count++] = records[i].category;
        }
    }

    *out_total = total;
    *out_unique_count = unique_count;
}

The fragment assumes n >= 0, records and unique_categories provide at least n accessible elements when n > 0, and both output pointers are non-null. It also assumes unique_categories does not overlap input storage in a way that changes unread records.

The first loop is a clean O(n). The second loop runs n times, and each iteration scans unique_categories, whose length grows up to k (the number of distinct categories, with k ≤ n) to check “have I already recorded this one?” In the worst case — every record has a different category — that inner scan costs O(n), making the whole second loop O(n²). By rule 1, sequential blocks combine by taking the larger term, so summarize is O(n) + O(n²) = O(n²) overall — even though, reading the code casually, you might say “it’s just two loops, so it’s O(n).”

Replacing the linear membership scan with a hash set gives expected O(1) membership and expected O(n) total time. When category codes occupy a small known range, a direct-address Boolean table provides deterministic constant-time membership at a space cost proportional to that range.

Summation Analysis

Nested loops do not automatically imply a product of their visible bounds. Write the total explicitly when iteration counts change. The next two fragments are mathematical pseudocode with unbounded counters; a direct fixed-width C translation must also guard the final increment or doubling against overflow.

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
        ++count;
    }
}

The inner body executes:

By contrast:

for (int i = 1; i <= n; i *= 2) {
    for (int j = 0; j < i; ++j) {
        ++count;
    }
}

executes 1+2+4+... up to n, a geometric series bounded by 2n, so the total is Theta(n), not Theta(n log n). Useful sums include:

Bounds can replace exact algebra: if at least half the terms of a monotone sum are each at least a constant fraction of the largest, the sum often has the order “number of terms times largest term.”

Cases

The running time of many algorithms depends not just on the size of the input but on its contents and arrangement. Searching for a value that happens to be the first element you check is fast; searching for one that isn’t there at all forces you to look everywhere. We distinguish three perspectives:

• Best case — the most favorable input of a given size. Useful for understanding an algorithm’s potential, but dangerous to rely on, since you rarely control your input.
• Worst case — the most unfavorable input of a given size. This is the perspective we adopt by default, because it gives you a guarantee: “no matter what you throw at this, it will not be slower than this bound.” Guarantees are what you build reliable systems on.
• Average case — expected running time under a stated input distribution. Quicksort is Theta(n log n) under standard randomized or average-case models despite a quadratic worst case. An average-case bound is only as trustworthy as its distribution assumption.

Linear search through an unsorted array has best-case time Theta(1) when the target is first and worst-case time Theta(n) when the target is last or absent. Conditional on a successful search whose target position is uniformly distributed, it performs (n + 1) / 2 comparisons on average, also Theta(n). Average-case analysis can produce a different asymptotic class for other algorithms; randomized quicksort, for example, has expected Theta(n log n) time and worst-case Theta(n^2) time.

C Examples

For each implementation, identify the input-size parameters, count the dominant operation, derive a sum or recurrence, and simplify it to a tight asymptotic bound.

Linear Search

int linear_search(const int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

The contract requires n >= 0 and a non-null array when n > 0. The input size is n, the number of elements. The loop inspects exactly n elements when the target is absent, so worst-case time is Theta(n). A first-position match takes Theta(1) time. The algorithm stores only a fixed number of scalars, giving Theta(1) auxiliary space.

Bubble Sort

void bubble_sort(int arr[], int n) {
    for (int pass = 0; pass < n - 1; pass++) {
        for (int i = 0; i < n - 1 - pass; i++) {
            if (arr[i] > arr[i + 1]) {
                int tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
            }
        }
    }
}

The inner loop runs n - 1 times on the first pass, then n - 2, then n - 3, down to 1. The total number of adjacent comparisons is:

That expression is quadratic, so the running time is Theta(n^2) for this version. The contract requires n >= 0 and a non-null array when n > 0. The algorithm is in-place, using Theta(1) auxiliary space. If a swapped flag stops after an unchanged pass, the best case becomes Theta(n) on an already sorted array, while the worst case remains Theta(n^2).

Binary Search

int binary_search(const int arr[], int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

Binary search requires n >= 0, a non-null array when n > 0, and non-decreasing array order. Each iteration discards about half of the remaining search range. After one iteration, at most n/2 elements remain; after two, at most n/4; after k, at most n / 2^k. The loop stops when that quantity drops below 1, so an unsuccessful search takes Theta(log n) iterations for n > 1; a midpoint match takes Theta(1). The iterative version uses Theta(1) auxiliary space.

Factorial Recurrence

long long factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

The function’s mathematical contract is 0 <= n <= 20; the upper bound ensures that the exact factorial fits in a typical 64-bit long long. This function performs one recursive call on an input that is smaller by 1. The recurrence is:

Expanding it gives T(n) = T(n - 2) + Theta(1) + Theta(1), then T(n - 3) + 3Theta(1), and so on until the base case. There are n + 1 calls when counting factorial(0), so running time and call-stack space are both Theta(n). The code does not enforce its contract; a production interface would reject negative or unrepresentable inputs instead of returning a misleading value.

Amortized Analysis

An individual operation may be expensive even when expensive operations are sufficiently infrequent that every long sequence has a small average cost. Amortized analysis bounds the total cost of an operation sequence and divides by the number of operations; it does not assume a probability distribution.

A dynamic array illustrates the distinction. When an append finds the backing buffer full, the array allocates a larger buffer—typically twice the previous capacity—and copies the existing elements.

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct {
    int *data;
    size_t length;
    size_t capacity;
} IntVector;

bool vector_push(IntVector *v, int value) {
    if (v == NULL || v->length > v->capacity ||
        (v->capacity > 0U && v->data == NULL)) {
        return false;
    }
    if (v->length == v->capacity) {
        if (v->capacity > SIZE_MAX / 2) {
            return false;
        }
        size_t new_capacity = (v->capacity == 0) ? 1 : v->capacity * 2;
        if (new_capacity > SIZE_MAX / sizeof(*v->data)) {
            return false;
        }
        int *resized = realloc(v->data, new_capacity * sizeof(*v->data));
        if (resized == NULL) {
            return false;
        }
        v->data = resized;
        v->capacity = new_capacity;
    }
    v->data[v->length++] = value;
    return true;
}

A resizing append costs Theta(n) when it copies n existing elements. Because capacity doubles, resizes occur after capacities 1, 2, 4, 8, and so on. After $n$ successful pushes, total copying over all resizes is less than:

$1 + 2 + 4 + 8 + \cdots + n \;\leq\; 2n$

This geometric sum is bounded by twice its largest term. Including the n ordinary writes gives Theta(n) total work for n pushes, so vector_push has Theta(1) amortized time even though one call may take Theta(n) time. Allocation failure is reported separately and does not change the operation-count argument for successful pushes.

Aggregate Method

The geometric-series argument is the aggregate method: bound the total cost T(n) of an entire sequence, then divide by its n operations. If n pushes perform n ordinary writes and fewer than 2n copied writes, T(n)<3n, so the amortized cost is less than three primitive writes per push.

Accounting Method

The accounting method assigns an artificial charge to each operation. Charge three credits per append: one pays for the immediate write, and saved credits on elements pay for their future copies during resizing. A valid accounting proof never lets the credit balance go negative. The charged cost may exceed one operation’s actual cost, but the accumulated overcharge pays for rare expensive operations.

Potential Method

The potential method stores prepaid work in a mathematical function Phi(state). The amortized cost of operation i is:

Summing telescopes:

If potential starts at zero and never becomes negative, total actual cost is no greater than total amortized cost. For a vector that only appends and doubles when full, let n be its current length, C its current capacity, and define

After the first allocation and after every doubling, the vector is at least half full, so Phi >= 0; the empty state has Phi(0,0)=0. Count one unit for writing an appended item and one unit for each copied item.

For an append that does not resize, actual cost is 1, length increases by one, and capacity is unchanged:

For an append to a full vector of length and capacity C, the operation copies C items, writes the new item, and changes the state from (C,C) to (C+1,2C). Its actual cost is C+1, but its potential falls from C to 2:

The expensive resize spends potential accumulated by earlier cheap appends. The special first append has constant amortized cost as well. Thus every successful append is charged at most a constant even though a resize copies a linear number of elements.

Amortized analysis is not average-case analysis. It makes no probability assumption about inputs; it guarantees the average cost over every valid operation sequence. It also does not promise that each operation has low latency—one resize remains individually linear.

If capacity grows by a fixed 10 positions, the copies form 10 + 20 + ... + Theta(n) = Theta(n^2). Dividing by n pushes gives Theta(n) amortized time per push. Geometric growth is therefore essential to the constant amortized bound.

Lower Bounds

An upper bound analyzes one algorithm. A lower bound proves that every algorithm in a stated model must perform at least some amount of work.

• Finding a maximum among n arbitrary values needs at least n-1 comparisons: every nonmaximum must lose at least once.
• Comparison sorting needs Omega(n log n) comparisons because a binary decision tree must distinguish n! input orders.
• Reading an unstructured input whose every element can affect the answer gives an Omega(n) information requirement.
• Writing k output items gives an Omega(k) output-size lower bound.

Lower bounds are model-dependent. Counting sort beats the comparison-sorting lower bound because it uses keys as array indices rather than learning order solely through pairwise comparisons.

The maximum-finding bound can be proved as an adversary argument. Initially every element could be the maximum. A comparison between two candidates can eliminate at most one candidate: the smaller one. To leave exactly one possible maximum, at least n - 1 candidates must lose, which requires at least n - 1 comparisons. A linear scan meets that bound exactly, so it is comparison-optimal even though a different representation or parallel machine might reduce elapsed depth.

The qualification “in the comparison model” matters. If values are known to be bits, one can combine machine words and exploit word-level parallelism; if the input is already accompanied by a certified maximum index, verification has a different contract. A lower bound never floats free of the information initially available and the operations an algorithm is permitted to use.

Time-Space Trade-Offs

Faster algorithms often store more information:

• a hash table replaces repeated linear membership scans with expected constant-time lookup;
• memoization stores solved recursive states;
• prefix sums spend Theta(n) preprocessing space to answer range-sum queries in Theta(1);
• Floyd–Warshall stores a V x V distance table to answer every-pair queries;
• an in-place sort saves memory but may sacrifice stability or worst-case speed.

State both input storage and auxiliary space clearly. An adjacency-list algorithm using O(V+E) total storage may use only O(V) additional traversal state because the graph itself is input. Recursion consumes stack space even without explicit allocation.

Analysis Pitfalls

Common analysis errors include the following:

• “It’s just a loop inside a loop, so it must be O(n²).” Not necessarily — if the inner loop’s range depends on the outer index and shrinks (as in has_duplicate above, or in many graph algorithms), the total work can be O(n) or O(n log n). Always do the sum, don’t just pattern-match on the shape of the code.
• “This library function is free.” Operations like strcat, strlen, memmove, or searching through a linked structure often hide a linear (or worse) scan inside a single, innocent-looking call. Calling strlen inside the condition of a loop that iterates over the same string is a classic way to silently turn an O(n) scan into an O(n²) one. Learn the cost of the standard-library functions you reach for — it’s some of the highest-leverage knowledge you can acquire.
• “Big-O tells me which algorithm to use.” It tells you how things will trend as n grows large — an essential, but not the only, ingredient in a real engineering decision. Constant factors, memory limits, code complexity, and the actual sizes of inputs you expect to see all matter too. Asymptotic analysis is a lens, not a verdict.
• Confusing the number of operations with the size of the numbers involved. An algorithm that does n additions of numbers with up to n digits each isn’t doing O(n) work in any meaningful physical sense — each addition itself costs more as the numbers grow. Most of the analysis in introductory courses (and in this one) assumes numbers fit in a fixed-size machine word — an int or long — an assumption called the unit-cost model. It’s worth knowing you’re making it.

Complexity Review

• Complexity requires an explicit input-size measure and cost model.
• Operation counts are simplified by retaining dominant growth, not by ignoring meaningful parameters.
• Big-O is an upper bound, Big-Omega a lower bound, and Big-Theta a tight bound.
• Best, average, and worst cases describe different quantifications over inputs of equal size.
• Summations reveal the true cost of varying nested loops.
• Aggregate, accounting, and potential methods prove amortized sequence bounds without probability assumptions.
• Lower bounds constrain all algorithms within a model; changing the model can evade a bound.
• Time, auxiliary space, preprocessing, output size, latency, and implementation constants all influence real selection.

Complexity Problems

Growth Practice

1. Put log log n, sqrt(n), n/log n, n, n log n, n^2, 2^n, and n! in increasing asymptotic order. Identify any pair whose order requires a short limit or inequality argument.
2. Prove directly from the definitions that 7n^2 + 3n + 12 is Theta(n^2) by supplying constants for both the upper and lower bounds.
3. Determine whether each statement is true: n = O(n^2), n^2 = O(n), 2n + 1 = Omega(n), log_2 n = Theta(log_10 n), and 2^n = O(3^n). Justify every answer from a definition or limit.
4. A program takes 0.8 seconds at n = 10,000. Estimate its time at n = 100,000 under linear, n log n, quadratic, and cubic models. State why these are scaling estimates rather than predictions of exact time.

Loop Accounting

5. Count the exact number of executions of the innermost statement in each fragment, then give a tight asymptotic bound:

   for (int i = 0; i < n; i++) {
       for (int j = i + 1; j < n; j++) {
           work();
       }
   }

   for (int width = 1; width < n; width *= 2) {
       for (int i = 0; i < n; i += width) {
           work();
       }
   }

6. Analyze sum_{i=1}^n floor(n/i). Derive an O(n log n) bound from the harmonic series and an Omega(n log n) bound using a suitable subset of its terms.

7. A loop repeatedly replaces positive integer x by x / 3. Express its iteration count in terms of the bit length of x, not just its numeric value.

8. Audit the claim “two consecutive loops mean O(n).” Give one example where it is true, one where hidden work makes it false, and the correct composition rule.

Cases and Models

9. For linear search, derive the expected number of comparisons when the target is present with probability p, its successful position is uniform, and an unsuccessful search examines all n items.
10. Explain why timing a function at only three input sizes cannot establish its asymptotic class. Design a benchmark that could distinguish likely linear, n log n, and quadratic growth while controlling warm-up, input distribution, and repeated measurements.
11. Analyze schoolbook addition and multiplication of two b-bit integers in a bit-cost model. Contrast those bounds with the word-RAM assumption used for fixed-width C integers.
12. A graph algorithm is reported as O(V^2). Describe a sparse and a dense family of graphs for which expressing the cost in both V and E would make comparisons more informative.

Sequence Costs

13. Starting from capacities 1,2,4,8,..., list the actual and amortized costs of the first eight vector appends using Phi(n,C)=2n-C. Verify that the potential never becomes negative.
14. Suppose a dynamic array grows by a factor r > 1 rather than by two. Bound the total number of copied elements after n appends as a function of r, and discuss the time-versus-unused-capacity trade-off as r approaches 1 or becomes large.
15. A binary counter stores k bits and increments by flipping trailing ones to zero and the next zero to one. Prove Theta(1) amortized flips per increment by both the aggregate method and a potential function.
16. Add deletion to the doubling vector. Explain why halving capacity as soon as length falls below capacity can thrash. Design separated growth and shrink thresholds and argue for constant amortized update time.

Information Limits

17. Prove that determining whether an unsorted array contains a zero requires inspecting all n positions in the worst case under a probe model where an algorithm learns a value only by reading it.
18. Prove the n - 1 comparison lower bound for finding a maximum, then design an algorithm that simultaneously finds the maximum and second maximum using n + ceil(log_2 n) - 2 comparisons when n is a power of two.
19. Give O(n log n)-time/O(1)-auxiliary-space and expected O(n)-time/O(n)-space solutions to two-sum. State overflow-safe C comparison rules when values and the target use signed 64-bit integers.
20. You receive an immutable array once, then must answer range-sum queries and point updates. Compare a prefix-sum array, direct scanning, and a tree-based index across preprocessing time, query time, update time, and space. Derive the workload conditions under which each representation is preferable.