3 ms·

You are using O(n) to measure the actual performance of an algorithm in practice. This is not the intention of O(n) -- rather it is used to classify functions i

You are using O(n) to measure the actual performance of an algorithm in practice. This is not the intention of O(n) -- rather it is used to classify functions into groups depending on "how they grow" with respect to the input as it goes to infinity. This is good because different instructions, or sequences of instructions, will perform differently across CPU architectures, for example two CPUs might have different cycles-per-instruction. Big-O makes claims independent of the hardware that remain true forever. Just because algorithm A is O(n) and B is O(n^2) does not mean that A will always outperform B.

gdxhyrd 7y ago
What you are missing is that " algorithm A is O(n)" is a meaningless statement unless you define under which operations.
baddox 7y ago
I’m not conflating big O notation with benchmarking. My point applies to theoretical models of computation. I’m pointing out that, for example, comparison sort is only O(n * lg n) in theory if the theoretical model of computation we’re dealing with can compare any two items in constant time. Comparing arbitrarily large integers can not be done in constant time in theory, so if that’s the problem we’re discussing then the complexity will not be O(n * lg n). But again, we generally are implicitly concerned with models of computation where comparison is a constant time operation.
lorenzhs 7y ago
No. Stop. That's not how this works. Yes, Big O notation measures asymptotic growth of functions. But what do those functions express? For them to express running times, you need to define a machine model. It's a model because it's not a real machine – we don't stroll into a computer shop and pick up some computer and use that as our reference. Instead, we define an abstract machine model. Often, that's the word RAM model which assumes that for an input size n, the machine can process words of size θ(log n) in constant time. This is reasonable close to how our actual computers work: 64-bit words, and we can do stuff with them in constant time. But it's not perfect, because the RAM model doesn't have any caches (let alone multiple levels of cache hierarchy), doesn't have disks, doesn't model the paging system, etc. If any of these things are of significant concern to you, pick a different model (e.g. an external-memory model to consider memory hierarchy, or look into cache-oblivious algorithms, ...). But talking about asymptotic running time without specifying which model you're using is absolutely pointless.

gdxhyrd 7y ago

What you are missing is that " algorithm A is O(n)" is a meaningless statement unless you define under which operations.

baddox 7y ago

I’m not conflating big O notation with benchmarking. My point applies to theoretical models of computation. I’m pointing out that, for example, comparison sort is only O(n * lg n) in theory if the theoretical model of computation we’re dealing with can compare any two items in constant time. Comparing arbitrarily large integers can not be done in constant time in theory, so if that’s the problem we’re discussing then the complexity will not be O(n * lg n). But again, we generally are implicitly concerned with models of computation where comparison is a constant time operation.

lorenzhs 7y ago

No. Stop. That's not how this works. Yes, Big O notation measures asymptotic growth of functions. But what do those functions express? For them to express running times, you need to define a machine model. It's a model because it's not a real machine – we don't stroll into a computer shop and pick up some computer and use that as our reference. Instead, we define an abstract machine model. Often, that's the word RAM model which assumes that for an input size n, the machine can process words of size θ(log n) in constant time. This is reasonable close to how our actual computers work: 64-bit words, and we can do stuff with them in constant time. But it's not perfect, because the RAM model doesn't have any caches (let alone multiple levels of cache hierarchy), doesn't have disks, doesn't model the paging system, etc. If any of these things are of significant concern to you, pick a different model (e.g. an external-memory model to consider memory hierarchy, or look into cache-oblivious algorithms, ...). But talking about asymptotic running time without specifying which model you're using is absolutely pointless.