I think that they main stumbling point for many people is the fact that Big-O notation is aimed asymptotically; in other words, it is only concerned about the performance of an algorithm (for example) when you have a bazillion items to process. If you're dealing with real-world (limited) cases, you need to pay attention to the constants-- those "uninteresting details" get interesting very quick.