🎓 A1Learner
🔍
0 of 100 lessons completed

DSA Counting Operations

Counting operations is a method that puts a counter inside the code to record each piece of work. The final count shows how the work grows as the input grows.

Counting a linear search

A linear search checks items one by one from the start. A comparison is one check of a value against the target, and this counter records each one.

names = ["Ana", "Bo", "Cy", "Dee"]
target = "Cy"
comparisons = 0
for name in names:
    comparisons += 1
    if name == target:
        break
print(comparisons)

The biggest term wins

This program runs one single loop and one nested loop at n = 10. The nested part supplies 100 of the 110 steps, so it dominates the count.

n = 10
single = 0
for i in range(n):
    single += 1
pairs = 0
for i in range(n):
    for j in range(n):
        pairs += 1
print(single, pairs, single + pairs)

Constants fall away

Two passes double the steps at every size, as both printed rows show. The growth still multiplies tenfold when n does, so the label stays O(n).

def count(n, passes):
    steps = 0
    for p in range(passes):
        for i in range(n):
            steps += 1
    return steps

print(count(10, 1), count(10, 2))
print(count(100, 1), count(100, 2))

Example

def search(values, target):
    comparisons = 0
    for i in range(len(values)):
        comparisons += 1
        if values[i] == target:
            return i, comparisons
    return -1, comparisons

scores = [34, 7, 23, 89, 12, 56, 41, 3, 78, 65]
print(search(scores, 34))
print(search(scores, 12))
print(search(scores, 100))

Key points

  • Counter: a variable that gains one for each operation being counted
  • A counter inside the code turns a growth claim into a printed number
  • Biggest term: the part of a count that grows fastest as n grows
  • Constant factor: a fixed multiplier on the work, like two passes instead of one
  • Big O keeps the biggest term and drops constant factors

In this example, a linear search runs three times on one list of ten scores. The first target sits at index 0 and costs one comparison. The second target sits in the middle and costs five comparisons. The third target is absent, so the search checks all ten values and returns -1. The counts grow with the position of the target, exactly as the printed pairs show.

Note

A counter changes nothing else in the code, so the counted run still gives the same answer.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A program does n + n^2 operations for an input of size n. Which term does Big O keep?