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?