Big-O notation is used to express what?

• A. Lower bound on resource usage.
• B. Exact running time for a specific input size.
• C. Upper bound on growth of running time or space with input size.
• D. Average-case resource usage.

Answer: (C)

Big-O notation describes how the resources an algorithm uses grow as the input size increases. It provides an upper bound on time or space in the worst case, focusing on the dominant growth rate and ignoring constants and less significant terms. This means it answers: as n gets large, how bad can the resource usage be at most, up to a constant factor?

Why that makes sense: it’s about scaling, not exact measurements for a particular input. It’s not a lower bound (that would be Omega) and not an average-case figure (which depends on input distribution and gives expected behavior). It’s also not a precise running time for a specific input, but a way to compare how different algorithms grow as inputs get bigger.

So the best description is that Big-O expresses an upper bound on the growth of running time or space with input size.