Every time I'm asked about big-O in a job interview, I'm asked to recite the formal rules of the notation, rather than demonstrate how to use the resulting insight to make the code better. Just because I don't know the formal rules of how to calculate Big-O they assume I can't write any code that scales.
Its like a teacher assuming a student can't speak english because he can't recite the adjective order chart from memory.
I guess I am saying don't underestimate the importance of rigor in knowing precise definition of mathematical notations.
On the other hand plenty of people can memorize that a lookup in a BST is O(log n) without understanding what that actually means. If you can explain that a balanced BST grows in height by powers of two without actually using the phrase "log n" then that's more impressive than the person who does rote memorization without understanding what it actually means.
So in the case of arrays, since we do not need to read A[0] and A[1] to access A[2], it makes more sense to say it is an O(1) operation.
Another example is arithmetic. Addition and multiplication are considered O(1) operations for many algorithms even though multiplication is slower than addition. At a lower level, addition could be considered O(log n), since the binary representation of numbers has O(log n) bits of input. But the abstraction of addition as an O(1) operation is more useful at a higher level.
Also in Big-O, we drop everything but the major term, so accessing element 0 may be O(1.0001) while accessing element 20 is O(1.0003), they are both still considered O(1).
This is purely my takeaway from my undergrad algorithms class, so it may not be entirely accurate. Please correct me if I am wrong or misleading.
On to the larger point: O(1) does not mean "twice as fast as O(2)". It means "does not take longer depending on how many elements there are". That is, if I have an algorithm that takes twice as long as an O(1) algorithm, the slower algorithm is still O(1). We do not care about constant factors when dealing with big-O notation.
Accessing an array is O(1). What do you have to do to access an array element? You have to take the size of an array element, and multiply it by the index of the element, and add the starting address of the array, and access the memory at that address. That's O(1), because it does not depend on the number of elements in the array.
In contrast, accessing an element in a linked list is O(N). You have to start at the beginning of the list, and keep getting the next element until you get to the one you want. On average, that takes N/2 operations for a list of N elements. But we don't care about constant factors like 1/2 in big-O notation, so accessing an element of a list is O(N).
But if I want to insert an element into the middle of a linked list, and I already have a pointer to the place where I want to insert it, that insertion is only O(1). I have to change swap some pointers around (2 or 4, depending on whether it's a singly- or doubly-linked list). But that doesn't depend on the size of the list. Whereas if I want to insert an element into the middle of an array, I have to move all the elements after the inserted item, which is an average of N/2 items, which means that operation is O(N).
This is a completely inadequate explanation of big-O, but I hope it's enough to clear things up at least a bit for you...
[Edit: fixed italics.]
Here is the key insight I was missing. Thank you very much!
Now, if the number of times you had to access the memory in order to retrieve the data in the array depended on how big the array was, then you'd have O(N). An array is specifically designed so you only have to go to memory twice, first to get the memory address stored at X position in the array, then to retrieve the information stored on that position.
A linked list, as described in a sibling comment, actually does have to do this. You trade easy accessibility for other properties.
Ditto for the steps to do register operations and any of the other machine language instructions. The time can vary, but not as a function of the size of the input. So it's still constant time.
To answer your immediate question, the "general computation model" assumes constant memory access time. It's hand-wavy, but at least it's consistent.
The bigger problem is that for hashtables, even under ideal, non-physical assumptions, you still can't logically derive O(1), because there are unavoidable, inherent computations you have to do as the hashtable gets arbitrarily large. Either you a) adapt the hash function to have a bigger output, or b) you allow values to stack up in each output slot. a) is log(n), b) is n.
I don't know anyone who could read the hashtable implementation, without knowing the "right" answer, who would reasonably say "oh, that's O(1), obviously".
I wondered about hashtables too. I was actually teaching someone about them recently and had to re-read some CS stuff for it, and in the process I realized that the O(1) access for hashtables doesn't make any sense in the light of explanations I know.
So it turns out that the answer is complicated and in CS curriculum they just handwave you through. It sucks, to be honest, and it's the one thing that always annoyed me about formal education - far too often the teacher/professor stated something as a fact and provided a "proof" with so much confidence that I sort-of assumed it must be so, and realized only months or years later (and after a lot of confusion) that I learned an approximation - maybe a smart one, with good reasons backing it up, but still just an approximation, with important caveats that were never even mentions.
It sorts of make you wonder how much do you really understand about things, even in STEM.
[0] - https://news.ycombinator.com/item?id=9808452
[1] - http://cs.stackexchange.com/questions/1643/how-can-we-assume...
I stated in my first reply that the growth rate is notated as a function of the size of the input. Big O is itself an approximation, you don't use it if you absolutely have to know all the other factors that don't vary on the size of the input. Such as if they vary on your memory architecture. In practice they tend not to matter, Big-O is sufficient for most purposes.
If you do need the detail, you remove the Big-O and write out your other factors so you can compare them to other algorithms at the right level of detail. There are also other notations you can use that convey other concepts, such as little-o, little-theta, big-theta. When you use a Landau symbol[1], as these are called, you're making an approximate statement by definition.
It's still perfectly fine to call array access O(1), even if your data is stored on Pluto, and it's Odysseus doing a space opera Odyssey for each retrieval, you're still only going there twice. Even if there are sub-algorithms that you are calling within the main one, you're still only calling them a constant number of times. If the first time you go to Pluto to get data it takes 6 months and the second time it takes 30 years, because of complications, it's still constant time.
If you were accessing a linked list stored on Pluto, then you're going to Pluto a number of times depending on how deep in the linked list your data is, assuming it's a dumb probe and it can't figure out where to go once it gets to Pluto and has to come back to earth to figure out what to do next. (go back to Pluto)
If it turns out retrieval time matters, or other factors besides the size of the input, then you can't approximate over them and Big-O ceases to be useful.
Given O(1) arithmatic, you should be able to use an O(1) hash function. At that point, you only have to deal with realocation as your tables grows without bound. You can solve that problem by using the 2n allocation method that gives us O(1) amortized appending to vectors.
Of course, you still need to make messy assumptions about randomness.
A hash function with 5 bits of output needs more operations than one with 2 bits of output.
Thanks everyone for chiming in and taking time to write your answers! I did know the general concepts behind O-notation, but no doubt I now understand it even better :).
In Isaac Asimov's biography he mentions taking some intelligence test (perhaps in the Army?) that checked for familiarity with advertising slogans. Sure, there was probably a correlation there, but know we realize that's fundamentally dumb.
In the same vein algorithmic complexity can be a fantastic first gentle introduction to theory and it's best when tied into writing algorithms in a data structures class. The same can be said about regexps for example - practical v theoretical aspects - or logic as applied with prolog (or even make) say.
The interesting thing (as seen in a comment below about arrays and constant big-O) is that often intuition goes against the the rigorous understanding - so it's best to have both. I suspect the same holds for language as well. For example etymology of word roots as well as actual writing using the words.