>(b) I use an O(log n) structure (such as a binary tree): since n is bounded by the size of physically addressable memory, this reduces to O(1). (See also rwmj's comment about memory access times. [1])
Uh, no. By definition, a O(log n) structure takes, on average, log n operations to get to the node you want to get to. That never reduces down to constant time, because any given access will take log n reads to get to the correct place.
Also, keep in mind that O(1) array lookup isn't really constant time. It's still variable, depending on where the information actually is stored(i.e. in the L2 cache, RAM, on HDD, etc.), the practical time can vary from double digit nanoseconds to several milliseconds. Cache misses can be hugely expensive.
O(log n) structure takes, on average, log n operations to get to the node you want to get to
Big-O notation is for asymptotic upper bounds, not the average case. That is, it's a guarantee that using the algorithm will never take longer than the function given. It is not a statement of the average case. In order to do that, you must make some analysis on the distribution of the inputs.
You're right that it's supposed to be the absolute upper bound. From a purely mathematical perspective, I agree completely. I wish I could edit my post to say:
>By definition, a O(log n) structure takes, for most inputs, no more than log n operations to get to the node you want to get to.
However, from a CS perspective, I still think that it's important to stress that the inputs do matter.
Big-O is not intended to be a worst-case analysis on running time. There are a lot of assumptions that go into the analysis on the inputs.
For example, it's generally accepted that binary search tree lookup is O(log n). However, if you have a very badly unbalanced tree, the lookup time could be O(n).
Sorry, but that's exactly what Big-O analysis is intended to do. If you have an binary search tree that can be imbalanced, then the lookup time is O(n). It's not "can be," it is. Worst-case analysis is across all inputs. Not "for most," but all.
The only binary search trees that people use in practice are balanced. That is, the algorithms that control insertion and deletion in the tree guarantee that the tree is always balanced, and they themselves run in O(log n) time. In my experience, most trees used in practice are in fact red-black trees, but a much easier to understand balanced binary tree is an AVL tree. So when we say that a red-black tree has O(log n) lookup, that is a guarantee across all inputs. There is no input to a red-black tree that will yield a linear lookup time.
O(f(n)) means that an operation takes less than k f(n) time to complete (where k is some constant) for all n.
I predicated my assertion on bounded memory, hence n is constant. Therefore O(log n) means that the operation is bounded in time by k log n. But since n is also a constant, this is equal to some other constant k'. This is equivalent to saying that the operation is bounded by O(1).
So you're arguing that all algorithms on a bounded-memory machine (that is, all of them) are O(1). Sure, but that constant in the O(1) is sufficiently large on most machines that this isn't useful to programmers who need to analyze the run times of their algorithms.
While strictly true, that is not a very useful approach to take. By the same reasoning, _every_ operation is either O(1) or does not terminate, because a system with bounded memory has a bounded number of possible states.
I can see why it's especially tempting to make that jump in the case of O(log n), but that's just not the way this type of analysis is performed - a more conventional way of stating your point would be to say "yes, it's theoretically worse than O(1) but for practical purposes the constant factors matter far more".
>I predicated my assertion on bounded memory, hence n is constant. Therefore O(log n) means that the operation is bounded in time by k log n. But since n is also a constant, this is equal to some other constant k'. This is equivalent to saying that the operation is bounded by O(1).
You're fundamentally misunderstanding what big-O notation means. You cannot say that since n has an upper limit, everything is constant. By your argument, the actual speed of an algorithm doesn't matter, period, since the sample size is bounded, which means that everything evaluates to a constant.
That's wrong.
Big-O notation is used to give a ballpark estimate of an algorithm's efficiency. In this case, the metric being used is the number of data fetches the CPU needs to get to the specific location that it's looking for.
O(1) means that the number of possible CPU instructions is constant, no matter how large n is. So a static array lookup is O(1) because, no matter how large N is, the CPU only has to do a fetch. That's 1 instruction, and while the actual time is variable due to cache misses, the total number of instructions is constant.
O(log n) means that it will take log n operations to get the result. Binary trees are a great example. Assuming a perfectly balanced BST, the worst possible number of lookups(i.e. to the farthest leaf) will be log n different fetches. If you have a system that creates 127 buckets, the worst possible number of lookup operations is 7, which is log base 2 of 128.
Big-O notation is used to give a ballpark estimate of an algorithm's efficiency.
No it's not. Big-O notation is used to denote asymptotic running times. The OP's question is invalid because his assumption of O(1) array accesses is only valid on hardware with finite memory size, which makes what is actually a O(log n) or O(n^(1/3)) memory read/write appear to be O(1).
I made the same invalid assumption and came to the same invalid conclusion as the OP (i.e. that language X has O(1) array accesses). You can't deny me this assumption (and therefore conclusion, which I reached logically) without denying it to the OP as well.
O(1) means that the number of possible CPU instructions is constant, no matter how large n is.
This is simply false. If n is larger than 2^32, the number of instructions (and more importantly, time) grows immensely.
Now if on the other hand you want to posit an infinite O(1) memory; OK, I posit a lambda calculus reducer which can treat infinitely sized terms as a single redux. Bam, I've got O(1) array accesses in lambda calculus (and thus functional programming) now.
Uh, no. By definition, a O(log n) structure takes, on average, log n operations to get to the node you want to get to. That never reduces down to constant time, because any given access will take log n reads to get to the correct place.
Also, keep in mind that O(1) array lookup isn't really constant time. It's still variable, depending on where the information actually is stored(i.e. in the L2 cache, RAM, on HDD, etc.), the practical time can vary from double digit nanoseconds to several milliseconds. Cache misses can be hugely expensive.