Time complexity
Complexity counts elementary operations as a function of input size $n$ — not “how many seconds on my laptop”.
Computers differ in clock speed. So we count basic steps (comparisons, additions, …) as a function $T(n)$ of input size. Storage complexity does the same for memory.
Runtime often depends on both $n$ and the particular values in the input.
Linear search
Scan a list of length $n$ for value $a$.
- If $a$ is first, you stop after 1 comparison.
- If $a$ is missing, you must look at all $n$ elements.
Same algorithm, very different runtimes depending on the input.
Key takeaways
- Complexity is about growth with $n$.
- Input values can change runtime.
- Count elementary operations, not wall-clock alone.