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

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.