Counting Operations

Overview

Counting operations means tallying the number of primitive steps — comparisons, assignments, arithmetic — an algorithm performs as a function of the input size n. It is the concrete measurement that asymptotic notation (Big-O) later abstracts.

Two algorithms that both produce correct output can differ by orders of magnitude in speed. Without counting operations, the only way to discover this is to run them on large inputs and hope you notice. Counting gives you a mathematical function T(n) that predicts performance before the code ever executes.

Where used: Interview prep: estimating whether an O(n^2) solution will pass within a 10^8 operations-per-second budget given constraints, Database query planning: the optimizer counts estimated disk reads and comparisons to choose the fastest execution plan

Why learn this

• It is the prerequisite for understanding Big-O notation — you cannot abstract what you have never concretely measured.
• Interviewers expect candidates to justify why one solution is faster by pointing to the exact operation count difference, not just naming a complexity class.
• It trains the habit of reading code structurally: seeing a nested loop and immediately recognizing n * n iterations rather than guessing.

Aha moment

# Algorithm A: linear scan
def find_max_a(arr):
    best = arr[0]        # 1 assignment
    for x in arr[1:]:    # n-1 iterations
        if x > best:     # 1 comparison each
            best = x     # 0 to n-1 assignments
    return best          # Total: between n and 2n-1 ops

# Algorithm B: sort then pick last
def find_max_b(arr):
    arr.sort()           # roughly n*log(n) comparisons
    return arr[-1]       # 1 access

Prediction: Both find the maximum — but how many operations does each actually do?

Common guess: They are about the same since both look at all elements.

Algorithm A does roughly n comparisons — one per element. Algorithm B sorts the entire array first, doing roughly n*log(n) comparisons plus n*log(n) swaps, only to grab a single element at the end. Counting operations reveals B does vastly more work than needed. The correct answer was already accessible in one pass.

Common mistakes

• Counting only one type of operation: Beginners often count comparisons but ignore assignments, or count loop iterations but forget the work done inside each iteration. The total cost is the sum of ALL primitive operations executed.
• Conflating lines of code with operations: A single line like 'a, b = b, a + b' contains two assignments and one addition — three operations, not one. Lines are a visual convenience; the CPU executes individual operations.
• Ignoring the cost of inner loops: When a loop runs n times and contains an inner loop that also runs n times, the total is n * n = n^2 operations, not n + n = 2n. Multiplication, not addition, is the rule for nested repetition.

Glossary

asymptotic notation

A mathematical way to describe how an algorithm's performance changes as input size grows.

primitive steps

The most basic, fundamental actions a computer can perform, like addition or comparison.

orders of magnitude

Significantly larger scale, typically measured in factors of ten (e.g., 10x, 100x, 1000x faster).

Recall questions

• What does T(n) represent when you count operations?
• Why do we count operations instead of measuring wall-clock time?
• A loop runs n times and each iteration contains a nested loop that runs n times. What is the total operation count, and why is it multiplication not addition?

Understanding checks

After this code runs for input size n, what is the value of count? Express it as a closed-form formula.

count = n*(n-1)/2. The inner loop runs 0 + 1 + 2 + ... + (n-1) times, which sums to n*(n-1)/2.

This is the classic triangular-sum pattern that appears in algorithms like insertion sort and bubble sort. Recognizing this sum immediately tells you the algorithm is O(n^2).

Two algorithms both solve the same problem: Algorithm A performs 5n + 20 operations and Algorithm B performs 2n^2 + 3 operations. For small n (say n = 3), B is faster. At what point does A become faster, and why does this matter?

Setting 5n + 20 = 2n^2 + 3 and solving gives a crossover around n = 4. Beyond that, A is faster and the gap grows rapidly. This matters because real-world inputs are typically large — what looks faster on toy inputs can be catastrophically slower at scale.

This illustrates why constant factors and lower-order terms matter for small inputs but the highest-degree term dominates at scale — the exact motivation for Big-O abstraction.

Practice tasks

Count the exact operations in a bubble sort pass

The starter code performs one pass of bubble sort on a 5-element array. Add a counter variable that increments on every comparison and every swap. Run it mentally (dry run) and predict the final counter value before checking.

Continue learning

Previous: What is an Algorithm?

Previous: Iteration & Traversal

Next: Big-O Notation

Next: Common Complexities

Return to DSA Roadmap