 Linear time

A time complexity bounded by $O(n)$ for input size $n$. A single pass with constant work per input entry has this bound.