Shaking every hand
O(n) — Linear
The analogy
You greet every guest at the door with one handshake each. Twice the guests, twice the handshaking — a straight line. Perfectly reasonable, and often the best you can do if you genuinely must look at everything.
Visualizer
Greeting every guest
step 1 / 10| Guests | · | · | · | · | · | · | · | · |
8 guests at the door. One handshake each.handshakes: 0
def greet_all(guests):
for g in guests:
shake(g) # exactly n handshakes
# 8 guests -> 8
# 16 guests -> 16 (doubles with n)
sum(values) # O(n)
max(values) # O(n)
x in a_list # O(n)Check yourself
Summing 2,000 numbers vs 1,000 takes roughly…