Think together · Start with a little story
The girl increases the number of cards from 10 to 100. The robot does not ask “Which computer?” It asks “How much does the number of checks increase?”
Lay out the process
- Check each itemAbout 10 to 100 checks
- Compare pairsMay grow to about 100 times as many
- Look at the trendMore input means more work
Time complexity describes how the amount of work grows with the input size.
It helps compare how quickly algorithms grow; it does not directly give a time in seconds. First understand what happens when the input doubles, then learn the notation.
01What does time complexity measure?
It does not directly say, “The program takes 0.2 seconds.”
Time complexity describes how the amount of work an algorithm needs grows as the input size n increases.
02Why not measure in seconds?
Elapsed time depends on the computer, compiler, system load, and other factors.
Complexity aims to describe a more stable pattern in how an algorithm’s work grows.
03What is the input size n?
It depends on the problem.
- For an array problem, n often means the number of elements.
- For a string problem, n often means its length.
- For a graph problem, there may be both V and E.
04Why ignore constants?
For example:
When n is large, the n term determines the growth pattern, not the leading 3 or the extra 10.
05Why ignore lower-order terms?
As n grows, n² increases much faster than n and the constant term.
06Does O(...) give the exact number of operations?
No.
07Does complexity only consider the worst case?
No. You can analyze the worst, average, or best case.
Algorithm problems often pay special attention to the worst case because it helps guarantee that any allowed input will not require far more work than expected.
What have you learned?
- Time complexity describes how work grows with the input size.
- It is not the actual running time in seconds.
- The meaning of n depends on the problem.
- Constants and lower-order terms are ignored when describing asymptotic growth.
- Big O is not an exact operation count.
- You can analyze best, average, and worst cases.
Next: What Is Big O Notation?
Your turn to try
If the input size doubles, does an O(n) algorithm always take exactly twice as long in seconds?
Ready? Open to see the explanation
No. O(n) describes how the amount of work grows asymptotically, not exact wall-clock time. Hardware and other factors still affect seconds.