What Is Big-O?

The Idea

Big-O describes how an algorithm's work grows as its input grows. It deliberately ignores hardware, language, and constant factors. What's left is the shape of the growth curve, and that shape is the only thing that survives when data gets big.

Real-World Example

Airport security is a fair comparison. Adding one more traveller barely changes the wait, but doubling the crowd roughly doubles it. The number on the clock matters far less than that relationship.

The Code

def total(nums):
    # one pass over n items -> work grows with n
    s = 0
    for x in nums:      # runs n times
        s += x
    return s

# n = 10   -> 10 additions
# n = 1000 -> 1000 additions
# We call this O(n): double the input, double the work.

nums = [4, 8, 15]
steps = 0
for x in nums:
  steps += 1
print(steps)