Introduction to Analysis of Algorithms

Algorithm analysis is a concept that I’ve always had a kind of reverent fear of, but it’s time to get down to it — even if it’s a 20,000-page article. Well, let’s talk about “analyzing” first. (We definitely know what an algorithm is — if not, check out this article: https://dev.to/m__mdy__m/what-is-an-algorithm-really-5agc
). In short, if we want to narrow down what “analysis” means, it means studying or examining something in a systematic way. When we say “algorithm analysis,” we mean that we want to evaluate an algorithm, examine it, and figure out what the best algorithm to write for our problem is or what the best algorithm to use is. We might also use other terms, like “algorithm review,” “algorithm consensus,” etc.

1.1 What is Correctness?

To show that an algorithm is correct, we must demonstrate that it does the thing it is supposed to do. The difficulty is that an algorithm unfolds over time and may perform a variable number of steps (loops, recursion, etc.), so we need a framework to reason about its behavior. A common framework for proving correctness of algorithms (and programs) is Hoare logic. Hoare logic relies on induction, invariants, and logical reasoning; here we will use these ideas informally.

We use two assertions called the precondition and the postcondition. By correctness we mean: whenever the precondition holds before the algorithm runs, the postcondition holds after it finishes. By termination we mean: whenever the precondition holds, the algorithm stops after a finite number of steps. If an algorithm satisfies the correctness assertion but we do not prove termination, we call that partial correctness. When we have both partial correctness and termination we call it total correctness. These terms connect a concrete problem specification to an algorithm that claims to solve it. Therefore we choose preconditions and postconditions to reflect the problem specification we want the algorithm to satisfy.

We can make these concepts more precise if we introduce a small standard notation. Boolean connectives: $\land$ means “and”, $\lor$ means “or”, and $\neg$ means “not”. We use $\rightarrow$ for Boolean implication (note that $(x \rightarrow y)$ is logically equivalent to $(\neg x \lor y)$ ), and $\leftrightarrow$ for logical equivalence ( $\alpha \leftrightarrow \beta$ abbreviates $(\alpha \rightarrow \beta) \land (\beta \rightarrow \alpha)$ ). Quantifiers: $\forall$ is universal quantification (“for all”), and $\exists$ is existential quantification (“there exists”). We often use the informal abbreviation “ $\Rightarrow$ ” to mean “implies” in English sentences (for example, “2 | x $\Rightarrow$ x is even”), while “ $\nRightarrow$ ” could be used to mean “does not imply”.

Now suppose $A$ is an algorithm and $I_A$ is the set of all well-formed inputs for $A$ . Intuitively, if $I \in I_A$ then it makes sense to feed input $I$ to algorithm $A$ . (We can formalize “well-formed” further, but intuition will do: e.g., an algorithm expecting a pair of integers should not be given a matrix.) Let $O = A(I)$ denote the output of $A$ on input $I$ , if an output exists. Let $\alpha_A$ be a precondition of $A$ and $\beta_A$ be a postcondition of $A$ . If input $I$ satisfies the precondition we write $\alpha_A(I)$ ; if output $O$ satisfies the postcondition we write $\beta_A(O)$ . Then partial correctness of $A$ with respect to $\alpha_A$ and $\beta_A$ can be expressed as:

$$\forall I \in I_A,\; \big(\alpha_A(I) \land \exists O\,(O = A(I))\big) \rightarrow \beta_A(A(I)).$$

In words: for every well-formed input $I$ , if $I$ satisfies the precondition and $A(I)$ produces an output (i.e., $A$ terminates on $I$ ), then that output satisfies the postcondition. Total correctness is (1.1) together with the additional claim that for all $I \in I_A$ , $A(I)$ terminates — so an $O$ with $O = A(I)$ always exists.

1.1. Modify (1.1) so it states total correctness.

A central concept in algorithm analysis is the loop invariant. A loop invariant is a statement that remains true after each execution of a loop body (for example, after every iteration of a while or for loop). Finding the right invariant and proving it is a creative task. If an algorithm terminates, a loop invariant helps prove $\alpha_A(I) \rightarrow \beta_A(A(I))$ . After establishing a correct loop invariant, we use it to prove partial correctness of the algorithm. Thus the criterion for choosing a loop invariant is that it should assist in proving the postcondition. In practice there may be many possible loop invariants (and correspondingly many choices of pre- and postconditions) that yield a valid correctness proof; the art lies in selecting useful ones. Typically, to show that a chosen invariant holds after each loop iteration we use induction, often relying on the precondition as an assumption in the induction step.

1.2 Why Analyze an Algorithm?

Ļere are several answers to this basic question, depending on one’s frame of reference: the intended use of the algorithm, the importance of the algorithm in relationship to others from both practical and theoretical standpoints, the difficulty of analysis, and the accuracy and precision of the required answer. Ļe most straightforward reason for analyzing an algorithm is to discover its characteristics in order to evaluate its suitability for various applications or compare it with other algorithms for the same application. Ļecharacteristics of interest are most often the primary resources of time and space, particularly time. Put simply, we want to know how long an implementation of a particular algorithm will run on a particular computer, and how much space it will require. We generally strive to keep the analysis independent of particular implementations—we concentrate instead on obtaining results for essential characteristics of the algorithm that can be used to derive
precise estimates of true resource requirements on various actual machines. In practice, achieving independence between an algorithm and characteristics of its implementation can be difficult to arrange. Ļe quality of the implementation and properties of compilers, machine architecture, and other major facets of the programming environment have dramatic effects on performance. We must be cognizant of such effects to be sure the results of analysis are useful. On the other hand, in some cases, analysis of an algorithm can help identify ways for it to take full advantage of the programming environment. Occasionally, some property other than time or space is of interest, and the focus of the analysis changes accordingly. For example, an algorithm on a mobile device might be studied to determine the effect upon battery life, or an algorithm for a numerical problem might be studied to determine how accurate an answer it can provide. Also, it is sometimes appropriate to address multiple resources in the analysis. For example, an algorithm that uses a large amount of memory may use much less time than an algorithm that gets by with very little memory. Indeed, one prime motivation for doing a careful analysis is to provide accurate information to help in making proper tradeoff decisions in such situations.

1.3 Theory of Algorithms

The prime goal of the theory of algorithms is to classify algorithms according to their performance characteristics. The following mathematical notations are convenient for doing so:

Definition: Given a function $f(N)$ ,

• $O(f(N))$ denotes the set of all $g(N)$ such that $|g(N)/f(N)|$ is bounded from above as $N \rightarrow \infty$ .

• $\Omega(f(N))$ denotes the set of all $g(N)$ such that $|g(N)/f(N)|$ is bounded from below by a (strictly) positive number as $N \rightarrow \infty$ .

• $\Theta(f(N))$ denotes the set of all $g(N)$ such that $|g(N)/f(N)|$ is bounded from both above and below as $N \rightarrow \infty$ .

These notations, adapted from classical analysis, were advocated for use in the analysis of algorithms in a paper by Knuth in 1976 [one | first]. They have come into widespread use for making mathematical statements about bounds on the performance of algorithms. The $O$ -notation provides a way to express an upper bound; the $\Omega$ -notation provides a way to express a lower bound; and the $\Theta$ -notation provides a way to express matching upper and lower bounds. In mathematics, the most common use of the $O$ -notation is in the context of asymptotic series.

In the theory of algorithms, the $O$ -notation is typically used for three purposes: to hide constants that might be irrelevant or inconvenient to compute, to express a relatively small “error” term in an expression describing the running time of an algorithm, and to bound the worst case. Nowadays, the $\Omega$ - and $\Theta$ -notations are directly associated with the theory of algorithms, though similar notations are used in mathematics.

Since constant factors are being ignored, derivation of mathematical results using these notations is simpler than if more precise answers are sought. For example, both the “natural” logarithm $\ln N \equiv \log_e N$ and the “binary” logarithm $\lg N \equiv \log_2 N$ often arise, but they are related by a constant factor, so we can refer to either as being $O(\log N)$ if we are not interested in more precision. More to the point, we might say that the running time of an algorithm is $\Theta(N \log N)$ seconds just based on an analysis of the frequency of execution of fundamental operations and an assumption that each operation takes a constant number of seconds on a given computer, without working out the precise value of the constant.

Example 1.4

Show that $f(N) = N \lg N + O(N)$ implies that $f(N) = \Theta(N \log N)$ .

As an illustration of the use of these notations to study the performance characteristics of algorithms, we consider methods for sorting a set of numbers in an array. The input is the numbers in the array, in arbitrary and unknown order; the output is the same numbers in the array, rearranged in ascending order. This is a well-studied and fundamental problem: we will consider an algorithm for solving it, then show that algorithm to be optimal in a precise technical sense.

First, we will show that it is possible to solve the sorting problem efficiently using a well-known recursive algorithm called mergesort. Mergesort, and nearly all of the algorithms treated in this book, are described in detail in Sedgewick and Wayne [30], so we give only a brief description here. Readers interested in further details on variants of the algorithms, implementations, and applications are encouraged to consult the books by:

• Cormen, Leiserson, Rivest, and Stein
• Sedgewick
• Knuth
• Gonnet and Baeza-Yates

Mergesort works as follows:

1. Divide: The array is split in the middle into two halves.
2. Conquer: Recursively sort each half.
3. Combine: Merge the two sorted halves together to produce the fully sorted array.

This is an example of the divide-and-conquer algorithm design paradigm, where a problem is solved by recursively solving smaller subproblems and using their solutions to solve the original problem. The recursive structure of algorithms like mergesort leads naturally to mathematical descriptions of their performance characteristics.

To accomplish the merge step efficiently, we use two auxiliary arrays, b and c, to hold the subarrays. For efficiency, it is best to declare these arrays external to the recursive method. Invoking the method with mergesort(a, 0, N-1) will sort the array {% katex inline %}a[0 \dots N-1]{% endkatex %}. After the recursive calls, the two halves of the array are sorted.

Then, we move:

• the first half of {% katex inline %}a{% endkatex %} to the auxiliary array b[]
• the second half of {% katex inline %}a{% endkatex %} to the auxiliary array c[]

We also add a sentinel value INFTY (assumed to be larger than all array elements) at the end of each auxiliary array. This ensures that once one array is exhausted, the remaining elements of the other array are moved into a[] without additional bounds checks.

The merge is then straightforward: for each index k from $lo$ to $hi$ , move the smaller of b[i] and c[j] into a[k], then increment the respective index i or j.

private void mergesort(int[] a, int lo, int hi) {
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;

    // Recursively sort the two halves
    mergesort(a, lo, mid);
    mergesort(a, mid + 1, hi);

    // Copy to auxiliary arrays
    for (int k = lo; k <= mid; k++)
        b[k - lo] = a[k];
    for (int k = mid + 1; k <= hi; k++)
        c[k - mid - 1] = a[k];

    // Add sentinels
    b[mid - lo + 1] = INFTY;
    c[hi - mid] = INFTY;

    // Merge back to a[]
    int i = 0, j = 0;
    for (int k = lo; k <= hi; k++) {
        if (c[j] < b[i]) 
            a[k] = c[j++];
        else 
            a[k] = b[i++];
    }
}

2 Analysis of Algorithms.

Although the analysis of sorting and merge sort that we have reviewed demonstrates the inherent "difficulty" of the sorting problem, there are many important questions about sorting (and merge sort) that it does not address at all. How long might an implementation of mergesort be expected to run on a particular computer? How might its running time compare to other O(NlogN) methods? (Ļere are many.) How does it compare to sorting methods that are fast on average, but perhaps not in the worst case? How does it compare to sorting methods that are not based on compares among elements? To answer such questions, a more detailed analysis is required. In this section we brieły describe the process of doing such an analysis. To analyze an algorithm, we must ŀrst identify the resources of primary interest so that the detailed analysis may be properly focused. We describe the process in terms of studying the running time since it is the resource most relevant here. A complete analysis of the running time of an algorithm involves the following steps:
• Implement the algorithm completely.
• Determine the time required for each basic operation.
• Identify unknown quantities that can be used to describe the frequency of execution of the basic operations.
• Develop a realistic model for the input to the program.
• Analyze the unknown quantities, assuming the modeled input.
• Calculate the total running time by multiplying the time by the frequency for each operation, then adding all the products.
Ļe ŀrst step in the analysis is to carefully implement the algorithm on a
particular computer. We reserve the term program to describe such an implementation. One algorithm corresponds to many programs. A particular implementation not only provides a concrete object to study, but also can give useful empirical data to aid in or to check the analysis. Presumably the implementation is designed to make efficient use of resources, but it is a mistake to overemphasize efficiency too early in the process. Indeed, a primary application for the analysis is to provide informed guidance toward better implementations. Ļe next step is to estimate the time required by each component instruction of the program. In principle and in practice, we can often do so with great precision, but the process is very dependent on the characteristics of the computer system being studied. Another approach is to simply run the program for small input sizes to “estimate” the values of the constants, or to do so indirectly in the aggregate.
Indeed, to determine the total running time of the program, it is necessary to study the branching structure of the program in order to express the frequency of execution of the component instructions in terms of unknown mathematical quantities. If the values of these quantities are known, then we can derive the running time of the entire program simply by multiplying the frequency and time requirements of each component instruction and adding these products. Many programming environments have tools that can simplify this task. At the ŀrst level of analysis, we concentrate on quantities that have large frequency values or that correspond to large costs; in principle the analysis can be reŀned to produce a fully detailed answer. We often refer to the “cost” of an algorithm as shorthand for the “value of the quantity in question” when the context allows. Ļe next step is to model the input to the program, to form a basis for the mathematical analysis of the instruction frequencies. Ļe values of the unknown frequencies are dependent on the input to the algorithm: the problem size (usually we name that N) is normally the primary parameter used to express our results, but the order or value of input data items ordinarily affects the running time as well. By “model,” we mean a precise description of typical inputs to the algorithm. For example, for sorting algorithms, it is normally convenient to assume that the inputs are randomly ordered and distinct, though the programs normally work even when the inputs are not distinct. Another possibility for sorting algorithms is to assume that the inputs are random numbers taken from a relatively large range. Ļese two models can be shown to be nearly equivalent. Most often, we use the simplest available model of “random” inputs, which is often realistic. Several different models can be used for the same algorithm: one model might be chosen to make the analysis as simple as possible; another model might better rełect the actual situation in which the program is to be used. Ļe last step is to analyze the unknown quantities, assuming the modeled input. For average-case analysis, we analyze the quantities individually, then multiply the averages by instruction times and add them to ŀnd the running time of the whole program. For worst-case analysis, it is usually difficult to get an exact result for the whole program, so we can only derive an upper bound, by multiplying worst-case values of the individual quantities by instruction times and summing the results. Ļis general scenario can successfully provide exact models in many situations. Knuth’s books are based on this precept. Unfortunately, the details in such an exact analysis are often daunting. Accordingly, we typically seek approximate models that we can use to estimate costs. Ļe ŀrst reason to approximate is that determining the cost details of all individual operations can be daunting in the context of the complex architectures and operating systems on modern computers. Accordingly, we typically study just a few quantities in the “inner loop” of our programs, implicitly hypothesizing that total cost is well estimated by analyzing just those quantities. Experienced programmers regularly “proŀle” their implementations to identify “bottlenecks,” which is a systematic way to identify such quantities. For example, we typically analyze compare-based sorting algorithms by just counting compares. Such an approach has the important side beneŀt that it is machine independent. Carefully analyzing the number of compares used by a sorting algorithm can enable us to predict performance on many different computers. Associated hypotheses are easily tested by experimentation, and we can reŀne them, in principle, when appropriate. For example, we might reŀne comparison-based models for sorting to include data movement, which may require taking caching effects into account.

2.1 Types of Cases in Algorithm Analysis

The analysis of algorithms necessarily involves considering different scenarios under which an algorithm might execute. When we examine an algorithm's performance, we typically distinguish among several types of cases, each providing distinct insights into the algorithm's behavior. These case analyses form the foundation of our understanding of algorithmic performance and allow us to make informed decisions about algorithm selection and optimization.

2.1.1 Worst-Case Analysis

The worst-case analysis of an algorithm determines the maximum number of steps (or resource consumption) that the algorithm could possibly require for any input of size $N$ . Formally, if we denote by $T(I)$ the running time of algorithm $A$ on input $I$ , and $I_N$ represents the set of all possible inputs of size $N$ , then the worst-case time complexity is:

$$T_{\text{worst}}(N) = \max_{I \in I_N} T(I).$$

Worst-case analysis is particularly important in safety-critical systems and real-time applications where we must guarantee that the algorithm completes within a specific time bound. For example, in avionics software or medical device control systems, knowing the absolute maximum execution time is essential for system reliability.

When we express worst-case complexity using asymptotic notation, we typically write $T_{\text{worst}}(N) = O(f(N))$ , meaning the worst-case running time grows no faster than $f(N)$ as $N$ becomes large. For mergesort, we can show that $T_{\text{worst}}(N) = O(N \log N)$ , which holds regardless of the initial arrangement of the input array.

The worst-case scenario often corresponds to a specific pathological input configuration. For instance, in quicksort with a naive pivot selection strategy, the worst case occurs when the array is already sorted or reverse-sorted, leading to $O(N^2)$ behavior. Identifying these worst-case inputs is itself an important part of algorithm analysis, as it can inform the design of better pivot selection strategies or other algorithmic improvements.

2.1.2 Best-Case Analysis

The best-case analysis examines the minimum number of steps required by an algorithm over all possible inputs of size $N$ . Formally:

$$T_{\text{best}}(N) = \min_{I \in I_N} T(I).$$

While best-case analysis might seem less practically useful than worst-case analysis, it provides valuable information in several contexts. First, it establishes a lower bound on algorithmic performance—no input can be processed faster than the best case. Second, for some algorithms, the best case occurs frequently enough in practice to be relevant. Third, understanding the best case helps us identify inputs that the algorithm handles particularly efficiently, which can inform preprocessing strategies or input transformation techniques.

Consider insertion sort as an example: its best-case running time is $\Theta(N)$ , occurring when the input array is already sorted. In this scenario, the algorithm makes exactly $N-1$ comparisons and performs no data movements beyond the overhead of the loop structure itself. This best-case behavior makes insertion sort an excellent choice for nearly-sorted data or for small arrays where the probability of encountering sorted or nearly-sorted inputs is high.

Best-case analysis is often denoted using $\Omega$ -notation. When we write $T_{\text{best}}(N) = \Omega(f(N))$ , we indicate that even in the most favorable circumstances, the algorithm requires at least $f(N)$ time.

2.1.3 Average-Case Analysis

Average-case analysis is perhaps the most practically relevant but also the most mathematically challenging type of analysis. It computes the expected running time of an algorithm over all possible inputs of size $N$ , weighted by the probability of encountering each input. If we assume a probability distribution $P$ over the input space $I_N$ , then:

$$T_{\text{avg}}(N) = \sum_{I \in I_N} P(I) \cdot T(I) = \mathbb{E}[T(I)],$$

where $\mathbb{E}$ denotes the expectation operator.

The mathematical techniques used for average-case analysis are broadly applicable to mathematical models in scientific applications ranging from genomics to statistical physics. Our prime motivation is to develop tools that enable precise statements about resource usage of important algorithms in practical applications. Average-case analysis is effective for two primary reasons.

The first reason is that straightforward models of randomness are often extremely accurate. Simple random models are effective in numerous practical scenarios:

• Sorting is fundamental in cryptanalysis, where adversaries ensure data appears indistinguishable from random.
• Commercial data processing systems routinely sort massive files where keys (account numbers, identification codes) are well modeled by uniformly random numbers.
• Computer network implementations depend on sorts involving keys that behave like random ones.
• Computational biology uses sorting extensively, where deviations from randomness warrant further scientific investigation into biological and physical processes.

When large datasets are created by humans, they typically involve arbitrary choices well modeled by random ones. Random models also prove effective with scientific data. We might interpret Einstein's assertion that "God does not play dice" to mean random models work precisely because significant deviations from randomness reveal something meaningful about the natural world.

The second reason average-case analysis is important is that we can often inject randomness into problem instances so they appear random to both the algorithm and analyst. This approach enables efficient algorithms with predictable performance, known as randomized algorithms. M. O. Rabin was among the first to articulate this methodology, which has been extensively developed by subsequent researchers.

We typically begin by analyzing random models, starting with computing the mean—the average value of some quantity of interest for $N$ instances drawn at random. Elementary probability theory offers several related approaches. We explicitly identify two:

Distributional Approach. Let $\mathcal{N}$ be the number of possible inputs of size $N$ and $\mathcal{N}_k$ be the number of inputs causing the algorithm to have cost $k$ , so $\mathcal{N} = \sum_k \mathcal{N}_k$ . The probability that cost is $k$ is $\mathcal{N}_k / \mathcal{N}$ , and expected cost is:

$$\frac{1}{\mathcal{N}} \sum_k k \mathcal{N}_k.$$

This analysis depends on counting: How many inputs exist of size $N$ , and how many cause cost $k$ ? These steps compute the probability distribution, making this the most direct approach from elementary probability theory.

Cumulative Approach. Let $\mathcal{T}_N$ be the total (cumulated) cost on all inputs of size $N$ . (That is, $\mathcal{T}_N = \sum_k k \mathcal{N}_k$ , but direct computation may proceed differently.) The average cost is simply $\mathcal{T}_N / \mathcal{N}$ . This analysis depends on a less specific counting problem: what is the total cost across all inputs? General tools make this approach very attractive.

The distributional approach provides complete information for computing standard deviation and other moments. Indirect, often simpler methods also exist for computing moments using the cumulative approach. We consider both, though we tend toward the cumulative method, which allows analyzing algorithms through combinatorial properties of basic data structures.

Many algorithms solve problems by recursively solving smaller subproblems, enabling derivation of recurrence relationships that average or total cost must satisfy. Direct recurrence derivation from the algorithm is often natural.

Average-case results are valuable because, where random input is reasonable, accurate analysis helps us:

• Compare different algorithms for the same task.
• Predict time and space requirements for specific applications.
• Compare different computers running the same algorithm.
• Adjust algorithm parameters to optimize performance.

Average-case results can be compared with empirical data to validate implementation, model, and analysis. The goal is gaining sufficient confidence to predict algorithm performance under whatever circumstances arise in particular applications. We can evaluate potential impacts of new machine architectures on important algorithms through analysis, perhaps before the architecture exists. This approach has been validated over decades: sorting algorithms first analyzed over fifty years ago remain useful for evaluating performance on contemporary computers.

For average-case complexity, we often write $T_{\text{avg}}(N) = \Theta(f(N))$ when the expected running time has tight asymptotic bounds, or $T_{\text{avg}}(N) = O(f(N))$ when we have only an upper bound on the expected performance.

2.1.4 Amortized Analysis

Amortized analysis differs fundamentally from the previous three cases. Rather than analyzing a single operation on a single input, amortized analysis considers the average cost per operation over a sequence of operations. The key insight is that while individual operations might occasionally be expensive, the total cost averaged over many operations remains low.

Formally, if we have a sequence of $m$ operations on a data structure initially of size $N$ , and the total cost of all $m$ operations is $T(m, N)$ , then the amortized cost per operation is:

$$T_{\text{amortized}} = \frac{T(m, N)}{m}.$$

Amortized analysis is particularly useful for analyzing data structures where occasional expensive operations are compensated by many cheap operations. The classic example is dynamic array resizing: when an array becomes full, we allocate a new array of double the size and copy all elements. Although this resize operation costs $\Theta(N)$ time, it happens infrequently enough that the amortized cost of insertion remains $O(1)$ .

There are three primary techniques for amortized analysis:

Aggregate Method. We compute the total cost of $m$ operations and divide by $m$ . For dynamic arrays with doubling, inserting $N$ elements requires copying $1 + 2 + 4 + \cdots + N$ elements total, which sums to $2N - 1$ . Thus the amortized cost per insertion is $(2N - 1)/N = O(1)$ .

Accounting Method. We assign different charges to different operations, some more and some less than their actual cost. The accumulated credit must always be non-negative and can be used to pay for expensive operations. For dynamic arrays, we might charge $3$ units per insertion: $1$ for the insertion itself, $1$ to pay for copying this element during the next resize, and $1$ to help pay for copying an element from the previous half of the array.

Potential Method. We define a potential function $\Phi$ mapping data structure states to non-negative real numbers. The amortized cost of operation $i$ is $c_i + \Phi(D_i) - \Phi(D_{i-1})$ , where $c_i$ is the actual cost and $D_i$ represents the data structure state after operation $i$ . If we choose $\Phi$ appropriately (increasing during cheap operations, decreasing during expensive ones), the amortized costs smooth out variations in actual costs.

It is crucial to understand that amortized cost is not the same as average-case cost. Average-case analysis considers a probability distribution over inputs, while amortized analysis considers the distribution of costs over a sequence of operations on a single input. An operation might have worst-case cost $O(N)$ , average-case cost $O(N)$ , yet amortized cost $O(1)$ when analyzed as part of a sequence.

Amortized analysis is typically expressed using the same asymptotic notations as other complexity measures. When we write that an operation has $O(1)$ amortized cost, we mean that over any sequence of $m$ operations, the total cost is $O(m)$ .

2.1.5 Relationships Among Cases

These four types of analysis are interconnected. For any algorithm and input size $N$ , we have:

$$T_{\text{best}}(N) \leq T_{\text{avg}}(N) \leq T_{\text{worst}}(N).$$

This inequality follows from the definition of minimum, average, and maximum. The average must fall between the extremes. However, the gaps between these values can vary dramatically depending on the algorithm. For some algorithms (like mergesort), all three are asymptotically equal: $T_{\text{best}}(N) = T_{\text{avg}}(N) = T_{\text{worst}}(N) = \Theta(N \log N)$ . For others (like quicksort), the best and average cases are $\Theta(N \log N)$ while the worst case is $\Theta(N^2)$ .

Amortized analysis occupies a different conceptual space since it analyzes sequences rather than single operations. Nevertheless, for a sequence of $m$ operations, we can define worst-case, average-case, and best-case amortized costs by considering different sequences or different probability distributions over sequences.

Understanding all four types of analysis provides comprehensive insight into algorithm behavior. Worst-case analysis guarantees performance bounds for critical systems. Best-case analysis identifies optimal scenarios and can guide preprocessing strategies. Average-case analysis predicts typical performance when inputs follow reasonable probability distributions. Amortized analysis reveals hidden efficiency in data structures where occasional expensive operations are offset by frequent cheap ones. Together, these tools enable us to select, optimize, and reason about algorithms with precision and confidence.

3 Time Complexity of Algorithms

Understanding how an algorithm's running time grows as input size increases is fundamental to algorithm analysis. This growth rate, independent of machine-specific constants, allows us to classify and compare algorithms systematically.

Definition (Informal). A function $f(n)$ such that the running time $T(n)$ of a given algorithm is $\Theta(f(n))$ measures the time complexity of the algorithm.

An algorithm is called polynomial time if its running time $T(n)$ is $O(n^k)$ where $k$ is some fixed positive integer. A computational problem is considered intractable if and only if no deterministic algorithm with polynomial time complexity exists for it. But many problems are classed as intractable only because a polynomial solution is unknown, and it is a very challenging task to find such a solution for one of them.

Table 3.1 shows how the running time $T(n)$ of algorithms having different time complexities changes as input size grows. Each row assumes that $T(8) = 1$ as a baseline, then shows how $T(n)$ grows for larger inputs. The dramatic differences in growth rates—particularly the explosive growth of exponential algorithms—illustrate why algorithmic efficiency matters profoundly in practice.

Table 3.1: Relative growth of running time $T(n)$ when the input size increases from $n = 8$ to $n = 1024$ , provided that $T(8) = 1$ .

Time Complexity	Notation	$n = 8$	$n = 32$	$n = 128$	$n = 1024$	Function
Constant	$1$	1	1	1	1	$1$
Logarithmic	$\lg n$	1	1.67	2.33	3.33	$\lg n / 3$
Log-squared	$\lg^2 n$	1	2.78	5.44	11.1	$\lg^2 n / 9$
Linear	$n$	1	4	16	128	$n / 8$
Linearithmic	$n \lg n$	1	6.67	37.3	427	$n \lg n / 24$
Quadratic	$n^2$	1	16	256	16,384	$n^2 / 64$
Cubic	$n^3$	1	64	4,096	2,097,152	$n^3 / 512$
Exponential	$2^n$	1	16,777,216	$2^{125}$	$2^{1021}$	$2^{n-3}$

Notice how dramatically different algorithms scale: when input size increases from 8 to 1024 (a 128-fold increase), a linear algorithm takes 128 times longer, while a quadratic algorithm takes 16,384 times longer. An exponential algorithm becomes utterly impractical— $2^{1021}$ is astronomically large, far exceeding the number of atoms in the observable universe. This table vividly demonstrates why we prefer $O(n \lg n)$ sorting algorithms over $O(n^2)$ ones for large datasets, and why exponential-time algorithms are generally infeasible except for very small inputs.

---

3.2 Example: Analysis of Quicksort

To illustrate the basic method just sketched, we examine next a particular algorithm of considerable importance, the quicksort sorting method. This method was invented in 1962 by C. A. R. Hoare, whose paper is an early and outstanding example in the analysis of algorithms. The analysis is also covered in great detail in Sedgewick; we give highlights here.

It is worthwhile to study this analysis in detail not just because this sorting method is widely used and the analytic results are directly relevant to practice, but also because the analysis itself is illustrative of many things that we will encounter later in the book. In particular, it turns out that the same analysis applies to the study of basic properties of tree structures, which are of broad interest and applicability. More generally, our analysis of quicksort is indicative of how we go about analyzing a broad class of recursive programs.

The Quicksort Algorithm

Program 3.3 is an implementation of quicksort in Java. It is a recursive program that sorts the numbers in an array by partitioning it into two independent (smaller) parts, then sorting those parts. Obviously, the recursion should terminate when empty subarrays are encountered, but our implementation also stops with subarrays of size 1. This detail might seem inconsequential at first blush, but, as we will see, the very nature of recursion ensures that the program will be used for a large number of small files, and substantial performance gains can be achieved with simple improvements of this sort.

The partitioning process puts the element that was in the last position in the array (the partitioning element) into its correct position, with all smaller elements before it and all larger elements after it. The program accomplishes this by maintaining two pointers: one scanning from the left, one from the right. The left pointer is incremented until an element larger than the partitioning element is found; the right pointer is decremented until an element smaller than the partitioning element is found. These two elements are exchanged, and the process continues until the pointers meet, which defines where the partitioning element is put. After partitioning, the program exchanges a[i] with a[hi] to put the partitioning element into position.

Program 3.3: Quicksort implementation in Java

private void quicksort(int[] a, int lo, int hi)
{
    if (hi <= lo) return;
    int i = lo-1, j = hi;
    int t, v = a[hi];
    while (true)
    {
        while (a[++i] < v) ;
        while (v < a[--j]) if (j == lo) break;
        if (i >= j) break;
        t = a[i]; a[i] = a[j]; a[j] = t;
    }
    t = a[i]; a[i] = a[hi]; a[hi] = t;
    quicksort(a, lo, i-1);
    quicksort(a, i+1, hi);
}

The call quicksort(a, 0, N-1) will sort the array. There are several ways to implement the general recursive strategy just outlined; the implementation described above is taken from Sedgewick and Wayne. For the purposes of analysis, we will be assuming that the array a contains randomly ordered, distinct numbers, but note that this code works properly for all inputs, including equal numbers. It is also possible to study this program under perhaps more realistic models allowing equal numbers, long string keys, and many other situations.

Analyzing Resource Requirements

Once we have an implementation, the first step in the analysis is to estimate the resource requirements of individual instructions for this program. This depends on characteristics of a particular computer, so we sketch the details. For example, the "inner loop" instruction while (a[++i] < v) ; might translate, on a typical computer, to assembly language instructions such as the following:

LOOP    INC  I,1        # increment i
        CMP  V,A(I)     # compare v with A(i)
        BL   LOOP       # branch if less

To start, we might say that one iteration of this loop might require four time units (one for each memory reference). On modern computers, the precise costs are more complicated to evaluate because of caching, pipelines, and other effects. The other instruction in the inner loop (that decrements j) is similar, but involves an extra test of whether j goes out of bounds. Since this extra test can be removed via sentinels, we will ignore the extra complication it presents.

Defining Key Variables

The next step in the analysis is to assign variable names to the frequency of execution of the instructions in the program. Normally there are only a few true variables involved: the frequencies of execution of all the instructions can be expressed in terms of these few. Also, it is desirable to relate the variables to the algorithm itself, not any particular program. For quicksort, three natural quantities are involved:

• $A$ – the number of partitioning stages
• $B$ – the number of exchanges
• $C$ – the number of compares

On a typical computer, the total running time of quicksort might be expressed with a formula, such as:

$$T(N) = 4C + 11B + 35A.$$

The exact values of these coefficients depend on the machine language program produced by the compiler as well as the properties of the machine being used; the values given above are typical. Such expressions are quite useful in comparing different algorithms implemented on the same machine. Indeed, the reason that quicksort is of practical interest even though mergesort is "optimal" is that the cost per compare (the coefficient of $C$ ) is likely to be significantly lower for quicksort than for mergesort, which leads to significantly shorter running times in typical practical applications.

Average-Case Analysis

Theorem (Quicksort analysis). Quicksort uses, on the average, $(N - 1)/2$ partitioning stages, $2(N + 1)(H_{N+1} - 3/2) \approx 2N\ln N - 1.846N$ compares, and $(N + 1)(H_{N+1} - 3)/3 + 1 \approx 0.333N\ln N - 0.865N$ exchanges to sort an array of $N$ randomly ordered distinct elements.

Proof. The exact answers here are expressed in terms of the harmonic numbers $H_N = \sum_{1 \leq k \leq N} 1/k$ , the first of many well-known "special" number sequences that we will encounter in the analysis of algorithms. As with mergesort, the analysis of quicksort involves defining and solving recurrence relations that mirror directly the recursive nature of the algorithm. But, in this case, the recurrences must be based on probabilistic statements about the inputs.

If $C_N$ is the average number of compares to sort $N$ elements, we have $C_0 = C_1 = 0$ and

$$C_N = N + 1 + \frac{1}{N} \sum_{1 \leq j \leq N} (C_{j-1} + C_{N-j}), \quad \text{for } N > 1.$$

To get the total average number of compares, we add the number of compares for the first partitioning stage ( $N + 1$ ) to the number of compares used for the subarrays after partitioning. When the partitioning element is the $j$ th largest (which occurs with probability $1/N$ for each $1 \leq j \leq N$ ), the subarrays after partitioning are of size $j - 1$ and $N - j$ .

Now the analysis has been reduced to a mathematical problem that does not depend on properties of the program or the algorithm. This recurrence relation is somewhat more complicated than (1.1) because the right-hand side depends directly on the history of all the previous values, not just a few. Still, is not difficult to solve: first change $j$ to $N - j + 1$ in the second part of the sum to get

$$C_N = N + 1 + \frac{2}{N} \sum_{1 \leq j \leq N} C_{j-1}, \quad \text{for } N > 0.$$

Then multiply by $N$ and subtract the same formula for $N - 1$ to eliminate the sum:

$$NC_N - (N - 1)C_{N-1} = 2N + 2C_{N-1}, \quad \text{for } N > 1.$$

Now rearrange terms to get a simple recurrence:

$$NC_N = (N + 1)C_{N-1} + 2N, \quad \text{for } N > 1.$$

This can be solved by dividing both sides by $N(N + 1)$ :

$$\frac{C_N}{N + 1} = \frac{C_{N-1}}{N} + \frac{2}{N + 1}, \quad \text{for } N > 1.$$

Iterating, we are left with the sum

$$\frac{C_N}{N + 1} = \frac{C_1}{2} + 2\sum_{3 \leq k \leq N+1} \frac{1}{k}$$

which completes the proof, since $C_1 = 0$ . As implemented earlier, every element is used for partitioning exactly once, so the number of stages is always $N$ ; the average number of exchanges can be found from these results by first calculating the average number of exchanges on the first partitioning stage. The stated approximations follow from the well-known approximation to the harmonic number $H_N \approx \ln N + 0.57721\ldots$ (the Euler-Mascheroni constant). We consider such approximations below and in detail in Chapter 4. $\square$

This analysis reveals that quicksort performs approximately $2N \ln N$ compares on average, which is only about 39% more than the theoretical minimum of $N \lg N$ compares required by any comparison-based sorting algorithm. Combined with its low overhead per comparison (the small coefficient in equation), quicksort achieves excellent practical performance despite lacking the worst-case guarantee of mergesort.

Concluding Remarks

The analysis of quicksort presented in Section 3.2, with its intricate recurrence relations and harmonic number summations, exemplifies both the power and the challenge of rigorous algorithm analysis. We have witnessed how a deceptively simple recursive partitioning strategy unfolds into a sophisticated mathematical framework requiring techniques from probability theory, combinatorics, and asymptotic analysis. The journey from Hoare's elegant 1962 invention to the precise statement that quicksort performs approximately $2N \ln N$ comparisons on average illustrates the depth of insight that careful analysis can provide—and hints at the vastness of what remains unexplored.
Indeed, this article has necessarily omitted far more than it has covered. We have barely scratched the surface of space complexity analysis, have not touched upon the rich theory of lower bounds for computational problems, and have left entirely unexamined vast algorithmic paradigms such as dynamic programming, greedy algorithms, graph algorithms, and the profound connections between data structures and their associated operations. The analysis techniques we have introduced—loop invariants, recurrence solving, probabilistic averaging—extend to contexts we have not mentioned: parallel algorithms, randomized algorithms, online algorithms, approximation algorithms, and the intricate dance between theory and practice in algorithm engineering.
For those whose curiosity has been awakened rather than sated, the references cited throughout this text offer doorways to deeper understanding. Knuth's magisterial The Art of Computer Programming remains the gold standard for mathematical rigor in algorithm analysis. Sedgewick and Wayne provide accessible yet thorough treatments of practical algorithms and their implementations. Cormen, Leiserson, Rivest, and Stein's Introduction to Algorithms covers an encyclopedic range of topics with consistent clarity. Each of these works, and the many others cited in our references, represents decades of accumulated wisdom from the computer science community.
The beauty of algorithm analysis lies precisely in this: there is always more to discover. A simple question—"How fast does this algorithm run?"—can lead to elegant mathematical theorems, surprising connections between seemingly unrelated problems, and practical insights that transform how we build software systems. Every algorithm analyzed rigorously is a small victory for human understanding over computational complexity.
If this exploration has resonated with you, if you find yourself curious about the mathematics underlying the software that increasingly shapes our world, then this article has achieved its purpose. The journey from informal algorithmic thinking to precise mathematical reasoning is challenging, occasionally frustrating, but ultimately deeply rewarding. We invite you to continue this journey, to explore the references, to implement and analyze algorithms yourself, and to join the ongoing conversation about computational complexity that has animated computer science for over half a century.
Your thoughts, questions, critiques, and insights are valuable. If this article has sparked ideas or raised questions, consider sharing them in the comments below. Whether you found the material illuminating or perplexing, too elementary or too advanced, your feedback helps shape future discussions. And if you believe others might benefit from this introduction to algorithm analysis, a like or share helps this work reach fellow travelers on the path of computational understanding.

Reference:

1. Preview (PagePlace) — Preview of book (ISBN: 9780133373479).
   https://api.pageplace.de/preview/DT0400.9780133373479_A23602754/preview-9780133373479_A23602754.pdf

2. Logic Symbols — List — Logic symbols and notation (reference sheet / cheat-sheet).
   https://www.basicknowledge101.com/pdf/km/logic_symbols%20list.pdf

3. Soltys, M. & Kulinicz, ? — An Introduction to the Analysis of Algorithms (World Scientific, 2018) — PDF copy.
   https://lib.zu.edu.pk/ebookdata/Engineering/Data%20Science/An%20introduction%20to%20the%20analysis%20of%20algorithms-World%20Scientific%20Publishing%20Co%20Pte%20Ltd%20BY%20Soltys-Kulinicz,%20Michael%20-%20(2018).pdf

4. Introduction to the Analysis of Algorithms (PDF) — Lecture notes / textbook (site: erode-sengunthar.ac.in).
   https://erode-sengunthar.ac.in/wp-content/uploads/2023/07/Introduction-to-Analysis-of-Algorithms-2.pdf

5. Data Structures / Algorithms (DGW2) — Textbook PDF from University of Auckland (cs.auckland).
   https://www.cs.auckland.ac.nz/textbookCS220/ebook/DGW2.pdf