On the BigO notation, you have to remember is that it's an upper bound on the runtime. There is no guarantee other than the growth of the function.
It is a good framework to get you in the ballpark of the correct thing. Even usually 99% of the time it is right. But sometimes the arch bites back due to your data.