1 Algorithm Analysis and Big-O Notation

Foundations of Algorithm Analysis

Algorithm analysis studies how resource requirements change as the input grows. The two resources considered most often are time, measured by the number of basic operations, and space, measured by memory use.

An algorithm is a finite, precisely defined sequence of steps for solving a problem. Algorithmic thinking proceeds by:

1. Defining valid inputs and required outputs.

2. Choosing an appropriate representation for the data.

3. Identifying essential operations such as comparison, insertion, deletion, or lookup.

4. Designing steps that produce the correct result.

5. Analyzing correctness and efficiency.

The same task can have different costs depending on the representation and the data structure. Searching an unsorted array generally requires scanning elements one at a time. If the data is sorted, binary search can repeatedly discard half of the remaining elements. A balanced search tree or a hash table can also provide faster searches under appropriate assumptions.

A useful distinction is between an abstract data type (ADT) and a data structure. An abstract data type (ADT) specifies what operations mean, while a data structure specifies how those operations are implemented. A stack can therefore be implemented with an array or a linked list, with different memory and operation costs.

Takeaway: Analyze both the algorithmic steps and the representation that makes those steps possible.

Input Size, Cost Models, and Resources

Begin by defining the input size. It is commonly represented by $n$, but its meaning depends on the problem:

• For an array, $n$ may be the number of elements.

• For a string, $n$ may be the number of characters.

• For a graph, $n$ may be the number of vertices and $m$ the number of edges.

• For an integer, input size may be the number of bits used to represent it rather than its numerical value.

A cost model identifies the basic operations being counted. Arithmetic, assignment, comparison, and array access are often treated as constant-time operations in an introductory model. This is an approximation, because hardware, memory layout, caching, and language implementation can affect actual cost.

For a one-pass summation of an array, each of the $n$ elements is processed once. The runtime is therefore $\Theta(n)$. If the algorithm stores only a running total, its auxiliary space is $\Theta(1)$.

Keep three space measures separate:

• Input space stores the input itself.

• Auxiliary space is additional memory used by the algorithm.

• Total space is input space plus auxiliary space.

For example, modifying an array in place can use $\Theta(1)$ auxiliary space, while creating a second array of $n$ elements uses $\Theta(n)$ auxiliary space. A recursive algorithm may also use call-stack space proportional to its maximum recursion depth.

Takeaway: State what $n$ measures, what operations count, and whether a space bound refers to input, auxiliary, or total space.

Runtime Patterns and Growth Rates

Runtime complexity describes how computational work grows with input size. Combine the costs of program parts according to their control flow:

• Sequential statements add. A $\Theta(n)$ part followed by a $\Theta(n^2)$ part costs $\Theta(n+n^2)=\Theta(n^2)$.

• Consecutive loops add. Two separate loops of $n$ iterations cost $\Theta(n+n)=\Theta(n)$.

• Independent nested loops multiply. Two nested loops that each run $n$ times perform $\Theta(n^2)$ work.

• For conditionals, analyze the branch appropriate to the selected case; worst-case analysis uses the most expensive branch.

• Repeatedly halving or doubling a problem size commonly produces $\Theta(\log n)$.

To simplify an expression, remove constant multipliers, retain the fastest-growing term, and express the result asymptotically. For example:

• $7n+20$ becomes $\Theta(n)$.

• $4n^2+3n+9$ becomes $\Theta(n^2)$.

• $12\log n+5$ becomes $\Theta(\log n)$.

The logarithm base is normally omitted because changing bases changes the value only by a constant factor. Thus $\Theta(\log_2 n)$ and $\Theta(\log_{10} n)$ are both written as $\Theta(\log n)$.

Common growth rates, from generally more scalable to generally less scalable, are:

1. Constant: $\Theta(1)$, such as array access by index.

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

3. Linear: $\Theta(n)$, such as one pass through an array.

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

5. Quadratic: $\Theta(n^2)$, such as many pairwise comparisons.

6. Cubic: $\Theta(n^3)$, such as some three-level nested loops.

7. Exponential: $\Theta(2^n)$, such as enumerating many subsets.

8. Factorial: $\Theta(n!)$, such as enumerating permutations.

This ordering describes eventual growth. For small inputs, a higher-growth algorithm can sometimes run faster because of smaller constant factors.

Takeaway: Follow the control-flow structure, then discard constants and lower-order terms only after forming the total cost.

Asymptotic Bounds and Input Cases

Asymptotic notation describes growth for sufficiently large inputs while ignoring constant factors and lower-order terms.

Big-O gives an asymptotic upper bound. Formally, $T(n)$ is $O(f(n))$ if there are positive constants $c$ and $n_0$ such that

Big-Ω gives an asymptotic lower bound. Formally, $T(n)$ is $\Omega(f(n))$ if there are positive constants $c$ and $n_0$ such that

Big-Θ gives a tight bound. A function is $\Theta(f(n))$ when it is both $O(f(n))$ and $\Omega(f(n))$. For example, a loop that always processes exactly $n$ elements has runtime $\Theta(n)$, and therefore also has $O(n)$ and $\Omega(n)$ bounds.

If $T(n)=3n^2+5n+7$, then $T(n)=O(n^2)$ and, more tightly, $T(n)=\Theta(n^2)$. It is also technically $O(n^3)$, but that upper bound communicates less useful information.

Do not confuse a case analysis with an asymptotic notation. Sequential search in an array of $n$ elements has:

• Best case $\Theta(1)$ when the target is first.

• Worst case $\Theta(n)$ when the target is last or absent.

• Average case $\Theta(n)$ under a common uniform assumption, because about half the elements are examined on average.

An average-case result requires an explicit assumption about the input distribution. Worst-case analysis is preferable when a guaranteed bound matters.

Takeaway: Use $O$ for an upper bound, $\Omega$ for a lower bound, and $\Theta$ when the growth rate is tight; separately state whether the result is best-case, average-case, or worst-case.

Recurrences and Data-Structure Costs

Recursive algorithms call themselves on smaller instances. Their runtime is often expressed with a recurrence relation, and their space analysis must include the maximum call-stack depth.

Binary search performs constant additional work and continues with half the input:

The input can be halved only $\Theta(\log n)$ times before reaching size one, so binary search has runtime $\Theta(\log n)$.

Merge sort divides the input into two halves and performs $\Theta(n)$ work to merge the results:

This recurrence solves to $\Theta(n\log n)$. Its implementation also requires attention to the memory used during merging and to the recursion stack.

Complexity claims for data structures depend on the operation and on implementation assumptions:

• Array index access is typically $\Theta(1)$; searching an unsorted array is $\Theta(n)$; insertion near the beginning can be $\Theta(n)$ because elements may need to shift.

• A linked list can insert at a known position in $\Theta(1)$, but finding that position by traversal is generally $\Theta(n)$, and direct random access is not typically $\Theta(1)$.

• A stack typically supports push and pop in $\Theta(1)$ with an appropriate implementation.

• A queue can support enqueue and dequeue in $\Theta(1)$ with a circular array or a linked-list implementation that stores both ends.

• A balanced search tree typically supports search, insertion, and deletion in $\Theta(\log n)$ because its height remains logarithmic.

• A hash table commonly provides expected $\Theta(1)$ search, insertion, and deletion with a suitable hash function and controlled load factor, but the worst case can degrade to $\Theta(n)$.

Time and space can trade off. For example, extra memory for a hash table can reduce the expected time of repeated searches compared with scanning a list.

Takeaway: For recursion, analyze work across all calls and maximum depth; for data structures, attach every bound to a specific operation and its assumptions.

Interpreting Complexity in Practice

Asymptotic analysis is a model of scalability, not a complete prediction of elapsed time. It does not directly capture constant factors, cache behavior, allocation and garbage-collection costs, input distributions, parallelism, hardware differences, implementation errors, or input/output costs.

A quadratic algorithm may outperform a linearithmic algorithm on a small input, while the linearithmic algorithm generally scales better as the input becomes large. Similarly, two algorithms with the same $\Theta$ bound can differ substantially in practical runtime because of constant factors or memory behavior.

Before accepting a complexity claim, check four points:

1. What does the input-size variable measure?

2. Which operations does the cost model count?

3. Is the claim about the best, average, or worst case?

4. What implementation assumptions are required, such as sorted data, a balanced tree, controlled hash-table load, or a known pointer?

Use asymptotic analysis to compare scalability, then use testing or profiling to measure real implementations. A strong analysis makes its model and assumptions explicit.

Final takeaway: Complexity analysis is most useful when it connects a precise input definition and cost model to a justified bound, a stated case, and the data structure or implementation assumptions behind that bound.

• Space complexity