Big-O describes growth, not speed: O(n) means the cost grows at most in proportion to n for large n. Constants and smaller terms are dropped, so two O(n) algorithms can differ a lot in real time. See Binary search (O(log n)) and Amortized analysis.
Big-O
An upper bound on how an algorithm's cost grows with input size n, ignoring constants and lower-order terms.