Complexity Analysis of Known Algorithms

Complexity analysis is the discipline of measuring how an algorithm's resource consumption — most commonly time, but also space — scales as its input grows. Rather than measuring raw execution time in seconds (which depends on hardware, compiler, and load), we count the number of times a basic operation executes as a function of input size n, then classify that count using asymptotic notation. The three pillars of this analysis are Big O (an upper bound on growth), Omega Ω (a lower bound), and Theta Θ (a tight bound valid when upper and lower match within constant factors). Applying these tools to algorithms you already know — linear search, binary search, bubble sort, merge sort, and selection sort — both deepens understanding of those algorithms and builds the analytical muscle needed for any new algorithm you encounter. Each example below follows the same methodology: identify the basic operation, count it across best, worst, and average cases, and justify the resulting notation.

Complexity Analysis of Linear Search

Linear search examines elements of an array one by one, from the first position to the last, until it either finds the target value or exhausts the array. The basic operation is the comparison between the current element and the target. Because comparisons are what determine how long the algorithm runs, we count them.

• Best case — Ω(1): The target element sits at index 0. On the very first comparison the algorithm succeeds and returns. The number of comparisons is exactly 1, regardless of how large n is. This gives a lower bound of Ω(1) for the best-case scenario. For example, searching for 7 in [7, 3, 14, 9, 2] terminates after a single comparison.
• Worst case — O(n): The target is either at the last index or is not in the array at all. The algorithm must perform all n comparisons before concluding. The count grows linearly with n, yielding O(n). Searching for 99 in [7, 3, 14, 9, 2] requires five comparisons and ultimately fails.
• Average case — Θ(n): If we assume the target is equally likely to be at any of the n positions, the expected position is (n + 1) / 2, so on average roughly n / 2 comparisons are made. Since n / 2 differs from n only by a constant factor of 1/2, and asymptotic notation absorbs constant factors, the average case is Θ(n).

A critical observation is that the best case (Ω(1)) and the worst case (O(n)) are different, so there is no single Θ bound that applies to all inputs of linear search. We can say the worst-case complexity is Θ(n) and the best-case complexity is Θ(1), but these describe different input families. This distinction matters whenever you need to make guarantees: if you cannot predict where the target will be, you must plan for the O(n) worst case.

Complexity Analysis of Binary Search

Binary search requires a sorted array. It works by comparing the target against the middle element, then discarding the half of the array that cannot contain the target, repeating until the element is found or the search space collapses to zero. The basic operation is again the comparison, but now each comparison eliminates roughly half the remaining candidates.

• Best case — Ω(1): The target happens to be exactly the middle element of the array on the first probe. Only one comparison is needed. Searching for 8 in the sorted array [1, 3, 5, 8, 11, 14, 19] (middle index 3, value 8) terminates immediately.
• Worst case — O(log n): After each comparison the search space is halved. Starting from n elements, after one step we have ⌊n/2⌋, after two steps ⌊n/4⌋, and so on. The maximum number of steps before the space reaches size 1 is ⌊log₂ n⌋ + 1, which is O(log n). Searching for 1 in [1, 3, 5, 8, 11, 14, 19] requires three comparisons (probing 8, then 3, then 1).
• Average case — Θ(log n): For uniformly distributed queries over a sorted array of size n, the expected number of comparisons is also Θ(log n). The exact expected value is approximately log₂ n − 1, still logarithmic.

Because best and worst differ here too (Ω(1) vs. O(log n)), we cannot write a single Θ across all inputs, but the worst and average cases both converge to Θ(log n), which is the figure most commonly cited. An important practical caveat: binary search's O(log n) advantage over linear search assumes the array is already sorted. If sorting is required first, you pay at minimum O(n log n) for that step. In an application that performs many searches on a fixed dataset, the one-time sort cost is easily amortised; for a single search on unsorted data, linear search may actually be cheaper overall.

Complexity Analysis of Bubble Sort

Bubble sort repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order. After each full pass, the largest unsorted element has "bubbled" to its correct position at the end. The basic operation is the comparison of adjacent elements; swaps are secondary and happen at most as often as comparisons.

The classic nested-loop structure makes the quadratic behavior transparent:

for i from 0 to n-2:          // outer loop: n-1 passes
    for j from 0 to n-2-i:    // inner loop: shrinks each pass
        if A[j] > A[j+1]:
            swap(A[j], A[j+1])

The total number of comparisons is (n−1) + (n−2) + … + 1 = n(n−1)/2, which is Θ(n²) in all cases without an early-exit flag. With an optimized version that tracks whether any swap occurred during a pass and exits early if none did:

• Best case (optimized) — Ω(n): If the array is already sorted, the first pass makes n−1 comparisons, finds no swaps, and the flag causes immediate termination. Total comparisons: n−1, which is Ω(n). Example: [1, 2, 3, 4, 5] triggers zero swaps on the first pass and exits.
• Worst case — O(n²): A reverse-sorted array (e.g., [5, 4, 3, 2, 1]) requires all n(n−1)/2 comparisons and the same number of swaps. Every pass must run to completion, and no early exit is possible. This is O(n²).
• Average case — Θ(n²): For randomly ordered input, approximately half of all possible adjacent pairs are in the wrong order on average. The expected number of comparisons is still proportional to n², giving Θ(n²).

The nested loop structure is the direct cause of quadratic behavior: the outer loop iterates O(n) times, and for each outer iteration the inner loop iterates O(n) times (less a shrinking offset, but still proportional to n). Multiplying these gives O(n²). This reasoning — multiply the loop bounds — is a standard technique for quickly estimating complexity from code structure.

Complexity Analysis of Merge Sort

Merge sort is a divide-and-conquer algorithm. It recursively splits the array in half until each sub-array has one element (which is trivially sorted), then merges pairs of sorted sub-arrays back together. The basic operation during merging is the comparison used to decide which element from the two sub-arrays goes next into the output.

• Best case — Ω(n log n): Even when the input is already perfectly sorted, merge sort does not skip any work. It still performs all ⌈log₂ n⌉ levels of recursion, and at each level the total merging work across all sub-arrays at that level is O(n). The best case is therefore Ω(n log n) — there is no shortcut analogous to bubble sort's early-exit flag.
• Worst case — O(n log n): The divide phase always produces log₂ n levels. At each level, all merging steps together examine every element once, costing O(n) comparisons per level. Total: O(n log n). A reverse-sorted or adversarially constructed input does not push merge sort past this bound.
• Average case — Θ(n log n): Since best and worst are both Θ(n log n), the average case must also be Θ(n log n). This tight bound across all input distributions is one of merge sort's most valuable properties: its performance is predictable, unlike algorithms whose best and worst cases diverge dramatically.

The recurrence relation captures the structure formally. If T(n) is the number of comparisons for an array of size n:

T(n) = 2·T(n/2) + O(n)      // two recursive calls + linear merge
T(1) = O(1)                  // base case

By the Master Theorem (case 2, where the work at each level matches the recursion branching factor), this solves to T(n) = Θ(n log n). One important trade-off: the merge step requires allocating a temporary array to hold the merged output, so merge sort uses O(n) auxiliary space. For memory-constrained environments this cost must be weighed against the algorithm's guaranteed time efficiency.

Complexity Analysis of Selection Sort

Selection sort divides the array into a sorted prefix (initially empty) and an unsorted suffix. On each pass it scans the entire unsorted suffix to find its minimum element, then swaps that minimum to the front of the suffix, extending the sorted prefix by one. The basic operation is the comparison used during the scan.

for i from 0 to n-2:           // n-1 passes
    minIndex = i
    for j from i+1 to n-1:     // scan the unsorted suffix
        if A[j] < A[minIndex]:
            minIndex = j
    swap(A[i], A[minIndex])

On pass i (0-indexed), the inner loop runs n − i − 1 times. Summing across all passes: (n−1) + (n−2) + … + 1 = n(n−1)/2 comparisons — regardless of the input order.

• Best, worst, and average case — all Θ(n²): Because the inner loop always scans the full remaining suffix to guarantee it finds the minimum (even if the minimum happens to already be in the right place), the comparison count is always n(n−1)/2. There is no early exit and no input arrangement that reduces the work. This makes selection sort's complexity uniform: Θ(n²) in every scenario.
• Swaps — O(n): Despite the quadratic comparison cost, selection sort performs at most n−1 swaps (one per pass). This contrasts favorably with bubble sort, which can perform O(n²) swaps in the worst case. If swap operations are costly (e.g., writing to flash memory), selection sort's low swap count can be an advantage.

Selection sort illustrates a scenario where a single Θ bound covers all cases. To formally justify Θ(n²), we must show two things: first, that the comparison count is at most c·n² for some constant c (establishing O(n²)); and second, that it is at least c′·n² for some constant c′ (establishing Ω(n²)). Since the count is exactly n(n−1)/2 = n²/2 − n/2, both bounds hold with c = 1 and c′ = 1/4 (for sufficiently large n), confirming the tight Θ(n²) classification.

Deriving and Justifying Complexity Classifications: A Systematic Method

The analyses above all follow the same disciplined procedure. Internalizing these steps lets you tackle any new algorithm with confidence.

• Step 1 — Identify the basic operation. Choose the single operation that executes most frequently and whose count best characterizes the algorithm's runtime. For search algorithms this is typically a comparison against the target; for sorting algorithms it is a comparison between array elements (and sometimes a swap). The basic operation should be something whose cost per execution is constant (O(1)).
• Step 2 — Count executions as a function of n. Trace through the algorithm's control flow — loops, recursion, branching — and express the number of times the basic operation executes as a precise mathematical formula in terms of input size n. For nested loops, multiply the bounds. For recursion, set up a recurrence relation. Example: bubble sort's inner loop gives a sum that evaluates to n(n−1)/2.
• Step 3 — Apply asymptotic notation. Drop lower-order terms and constant coefficients from the formula. Confirm that the result fits within the constant-factor bounds of the intended complexity class. For n(n−1)/2: drop the lower-order −n/2 term, drop the coefficient 1/2, and the result is Θ(n²).
• Step 4 — Perform case analysis. Determine whether the count derived in steps 2–3 applies to all inputs (enabling a single Θ bound) or varies by input structure (requiring separate O and Ω for different cases). Selection sort's count is input-independent → single Θ. Linear search's count varies from 1 to n → separate bounds for best and worst cases.
• Step 5 — Validate with concrete examples. Trace the algorithm manually on small inputs (n = 4 or n = 5 is usually sufficient) and count the actual basic operation executions. Confirm this count matches your formula. If it does not, revisit steps 1–2.

The following table summarises the complexity classifications derived above for quick reference:

Two broader lessons emerge from studying these five algorithms together. First, the same asymptotic complexity class can hide very different practical behaviors: bubble sort and selection sort are both Θ(n²), but selection sort makes far fewer writes. Second, a guaranteed tight bound across all inputs (as in merge sort and selection sort) is often more valuable in practice than an algorithm that is fast in the best case but slow in the worst, because real-world workloads rarely look like best cases. Complexity analysis gives you the vocabulary and the tools to make these comparisons rigorously rather than by intuition alone.