CODEWITHSUNDEEP
big-o
user
user

Reputation: 719

Usage of Big O for speedup comparison

From an (excellent) answer at another SE site a statement was presented which I reacted on: "X is roughly O(10^4) times faster than Y".

From the context it was obvious that the meaning was something along the lines of "X is roughly 4 orders of magnitude faster than Y", but this got me thinking: What exactly does such a Big O statement mean? I was sure at first sight the two were not equivalent, but thinking about it I cannot get my head around what it means exactly.

Upvotes: 0

Views: 73

Answers (1)

Sneftel
Sneftel

Reputation: 41513

It means that asymptotically, X is either only faster than Y by a constant factor, or is slower than Y. (If it were big-Theta instead of big-O, it would unambiguously mean the first). As you've guessed, there's no real difference between O(eight bazillion) and O(1); so what this is saying is "The factor by which X is faster than Y does not grow as the input grows". It may, however, shrink, hence the ambiguity I mentioned.

Obviously that literal meaning is not what the original poster intended. There's an unfortunate tendency to put O() around formulas when talking about performance when what the person really means is "give or take a little, I haven't literally benchmarked it".

Upvotes: 1

Related Questions