01 Algorithm Analysis and Big-O Notation

A progressive guide to designing, proving, and analyzing algorithms using data structures, complexity measures, asymptotic notation, and recurrence analysis.

Algorithmic Thinking

Algorithmic thinking begins by modeling a problem precisely rather than immediately writing code. An algorithm is a finite, precise sequence of steps that transforms input into required output.

A reliable design process is:

Define the inputs, outputs, assumptions, and what counts as a valid solution.
Choose a representation, such as an array, linked list, tree, or hash table.
Identify the dominant operations: searching, inserting, deleting, sorting, or traversing.
Develop the method using iteration, recursion, divide and conquer, or greedy selection.
Prove that the method produces an acceptable result.
Analyze time and memory as the input grows.
Test ordinary, boundary, empty, duplicate, and very large inputs.

The same task can have very different costs depending on representation and method. To search a collection of $n$ values, linear search may inspect all $n$ items, binary search uses about $\log_2 n$ comparisons when the data is sorted, and hash-table lookup can be constant time on average under suitable assumptions.

Takeaway: Good algorithm design connects problem definition, representation, correctness, efficiency, and testing.

Abstract Data Types and Representations

An abstract data type separates observable behavior from implementation details. A stack, for example, can be implemented with an array or a linked list while preserving last in, first out behavior.

Common abstract data types include:

Stack: supports operations such as push, pop, and peek; its access rule is last in, first out.
Queue: returns elements in first in, first out order.
List: maintains an ordered sequence of elements.
Set: contains each element at most once.
Map or dictionary: stores key–value associations.
Priority queue: returns an element according to priority.

An implementation must preserve its representation invariant. For a binary search tree, a typical invariant is that keys in the left subtree are less than the node's key and keys in the right subtree are greater, subject to the chosen duplicate-key policy.

The implementation determines performance. Arrays support direct indexing, linked lists provide flexible connections between nodes, balanced search trees support ordered operations, and hash tables are designed for key-based access.

Takeaway: The ADT states what operations mean; the data structure determines how those operations are carried out and how much they cost.

Correctness Proofs

Correctness and efficiency answer different questions. An algorithm is correct when it terminates and produces the required output for every valid input. A fast algorithm can be incorrect, and a correct algorithm can be impractically slow.

A correctness argument commonly identifies:

Precondition: what must be true before execution.
Postcondition: what is guaranteed after execution.
Invariant: what remains true during execution.
Termination argument: why execution eventually stops.

For an iterative algorithm that scans an array to find its maximum, a suitable is: before each iteration, maximum is the largest element examined so far. It is true initially, is preserved when the next element is compared, and implies the result after every element has been examined.

A recursive proof commonly uses mathematical induction. The base case establishes correctness for the smallest input, and the inductive step shows that correctness for smaller inputs implies correctness for the current input. The recursive calls must also make progress toward a reachable base case.

Takeaway: Prove that an algorithm solves the intended problem before evaluating how efficiently it does so.

Time and

Before counting operations, define the input-size measure. The variable $n$ may represent the number of array elements, string characters, or tree nodes. A tree may also use $h$ for height, while a graph may use $V$ for vertices and $E$ for edges. For an integer, the relevant size may be the number of bits used to represent it.

focuses on the growth of basic operations. Distinguish among:

Best case: least work for an input of size $n$ .
Worst case: greatest work for an input of size $n$ .
Average case: expected work under a stated probability distribution.
Amortized cost: average cost per operation over a sequence, even when individual costs differ.

For linear search, the best case is $\Theta(1)$ when the target is first, while the worst case is $\Theta(n)$ when the target is last or absent. If no case is specified, state which case is being analyzed; worst-case analysis is common because it gives a guarantee for every input of a given size.

tracks memory growth. Distinguish input space, auxiliary space, and total space. A recursive traversal of a balanced tree may use $O(\log n)$ stack space, whereas traversal of a highly unbalanced tree may use $O(n)$ stack space.

Takeaway: A complexity claim is meaningful only after the input-size measure, case assumption, and resource being measured are clear.

Asymptotic Notation

Asymptotic notation compares growth for sufficiently large inputs while ignoring constant factors and lower-order terms. This makes comparisons less dependent on a particular machine or implementation.

gives an eventual upper bound. For example, $3n+7=O(n)$ .
gives an eventual lower bound. Reading all $n$ input elements requires $\Omega(n)$ time in cases where every element must be inspected.
gives a tight bound when both the upper and lower bounds match. For example, $5n^2+3n+10=\Theta(n^2)$ .

Common growth rates, from generally slower to faster, are:

$\Theta(1)$ : constant, such as array access by a known index.
$\Theta(\log n)$ : logarithmic, such as binary search in a sorted array.
$\Theta(n)$ : linear, such as scanning an array.
$\Theta(n\log n)$ : linearithmic, such as merge sort.
$\Theta(n^2)$ : quadratic, such as simple nested-loop comparisons.
$\Theta(n^3)$ : cubic, as in some three-dimensional computations.
$\Theta(2^n)$ : exponential, such as brute-force subset enumeration.
$\Theta(n!)$ : factorial, such as brute-force permutation enumeration.

These classes describe eventual growth, not exact speed for every input. A quadratic algorithm can be faster on very small inputs if its constant factors are smaller, but a linearithmic algorithm eventually grows more slowly.

Takeaway: Report the tightest useful asymptotic bound and retain the conditions under which it applies.

Analyzing Loops and Recursion

Analyze code by counting how often its dominant operations execute.

Sequential statements: add their costs, then retain the dominant term. For example, $\Theta(n)+\Theta(n^2)=\Theta(n^2)$ .
Single loops: a loop that runs $n$ times with constant work per iteration costs $\Theta(n)$ .
Doubling or halving loops: repeatedly replacing $i$ with $2i$ , or halving a quantity, usually gives $\Theta(\log n)$ iterations.
Nested loops: multiply costs when the bounds are independent. Two loops of $n$ iterations each cost $\Theta(n^2)$ .
Variable inner bounds: count the actual total, such as $1+2+\cdots+n=\Theta(n^2)$ .
Conditionals: for a worst-case bound, analyze the condition and the more expensive branch. Two branches of $\Theta(n)$ still give $\Theta(n)$ , not $\Theta(2n)$ .

For recursive code, write a that includes every recursive call and all nonrecursive work. Binary search has $T(n)=T(n/2)+\Theta(1)$ , yielding $\Theta(\log n)$ . Merge sort has $T(n)=2T(n/2)+\Theta(n)$ , yielding $\Theta(n\log n)$ . Recursion trees and the Master Theorem can solve many such recurrences.

Representative bounds depend on conditions:

Array indexing: $\Theta(1)$ when the index is known and valid.
Binary search: $O(\log n)$ when data is sorted and supports efficient indexing.
Hash-table lookup: $O(1)$ average and $O(n)$ worst case, depending on collisions and load factor.
Balanced search-tree search: $O(\log n)$ when height remains logarithmic.
Unbalanced search-tree search: $O(n)$ in the worst case.
Merge sort: $\Theta(n\log n)$ time, commonly with additional merging space.
Simple quadratic sorting methods: $\Theta(n^2)$ worst-case time.

Takeaway: Count actual iterations and recursive subproblems, then state the assumptions that justify the bound.

Practical Analysis Checklist

Use this checklist to produce a complete analysis:

What variable measures the input size?
Which operation is repeated most often?
How many times can each loop execute?
Are loops sequential, nested, or dependent on one another?
Does recursion reduce the problem size, and by how much?
Which best-case, worst-case, or average-case assumptions apply?
How much auxiliary memory is required?
Is the reported bound an upper bound or a tight bound?
Which representation invariants must remain true?
Has correctness been justified independently of efficiency?

A useful final analysis might say that an algorithm takes $\Theta(n\log n)$ time and $O(n)$ auxiliary space in the worst case, under a specified representation and input-size definition. The statement is stronger than a bare complexity class because it identifies the resource, case, conditions, and meaning of $n$ .

Final takeaway: Algorithm analysis combines problem modeling, data-structure selection, correctness reasoning, and resource measurement. Use the representation that supports the required operations, prove the result separately from its cost, and express growth with the most informative bound available.