Big O isn't fooling you, it's giving you a one-function explanation of how the algorithm runs on an idealized system as the size of the problem increases. There

Big O isn't fooling you, it's giving you a one-function explanation of how the algorithm runs on an idealized system as the size of the problem increases. There's other systems you can simulate for big O, but the math is much harder and you wouldn't generally use it unless you're doing something complex like a cache-oblivious algorithm. If you're using solely big O to decide on an algorithm, you're fooling yourself. If performance is an issue, profile, benchmark, study, don't guess.