What does Big-O notation describe?
Options
- The exact running time of a program in seconds
- How time or memory grows as the input size grows (Correct option)
- The size of the source code, measured in lines
- The number of bugs a program has in total
Answer
How the running time (or memory) grows as the input size grows
Why
Big-O ignores machine speed and small details and answers: if the input becomes 10 times bigger, how much more work is needed?
- O(1): constant, same work for any size.
- O(log n): grows very slowly.
- O(n): grows in proportion.
- O(n²): 10× input → 100× work.
It usually describes the worst case.
Remember
Big-O = how cost grows with input size.