Big O: describing growth

Learning objectives

• Explain O(1), O(n), and O(n²) as growth categories.
• State both time and extra-space costs for a simple loop.

Count important work

found = false
for each value in values:
    if value equals target:
        found = true

In the worst case, this examines every one of n values, so its time grows linearly: O(n). It uses a fixed number of extra variables, so its auxiliary space is O(1). If two nested loops each traverse n values, the body can run about n×n times, O(n²).

What Big O does not say

It suppresses constant factors and hardware details. Two O(n) algorithms can have very different measured times. Big O is still useful because it warns how an approach behaves when the input becomes much larger.

Common mistakes

• Do not claim O(1) because one test looks short; count how often it runs.
• Say whether a cost is worst-case, average-case, or amortized when that distinction matters.

References

• OpenDSA: analysis introduction