5 ms·

I don't think it's necessary to know the formal definition of big O (or big Theta or big Omega) but there's a spectrum there. If all you can say is "nested for

by mason55 11y ago

I don't think it's necessary to know the formal definition of big O (or big Theta or big Omega) but there's a spectrum there. If all you can say is "nested for loops are bad" and you can't explain why hash tables provide fast lookups then I'm not going to be very impressed. 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.

TeMPOraL 11y ago
I'm going to render myself permanently unemployable in the industry by admitting this, but one thing I'm still not really sure about is why every text on CS assumes array have O(1) access? I mean, in the real world it surely takes more time to reach elements further in memory, if only because electrons travel at finite speeds and also you can't magically write any number into a register, there has to be a piece of electronics that will count up to it somehow. Is it only because all those hardware operations are so stupidly fast we don't care about them day-to-day usage, or is there another reason for assuming arrays have O(1) access?
- xKingfisher 11y ago
  My understanding from my algorithms class is that it is simply a matter of choosing your abstraction. Big O is meant to provide a general framework for qualifying and comparing algorithms free of machine dependent factors like execution time. It is not possible to account for every possible facet of every operation so some operations are chosen to be O(1) even though in reality they take multiple machine code instructions or have slightly varying real world performance. Saying array access is O(1) also does not account for different architectures or cache misses, which have major performance implications. 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.
- AnimalMuppet 11y ago
  First, no, in the real world it does not take more time to reach elements further in memory. Even if the memory is physically further on a chip (and some memory has to be), the memory transfer happens on a clock edge, not just "as soon as possible", so the elements actually transfer at the same time. 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.]
  - TeMPOraL 11y ago
    > Even if the memory is physically further on a chip (and some memory has to be), the memory transfer happens on a clock edge, not just "as soon as possible", so the elements actually transfer at the same time. Here is the key insight I was missing. Thank you very much!
  - Terr_ 11y ago
    It'd be amusing if asynchronous processors suddenly took off and many Big-O questions became trickier.
- vinceguidry 11y ago
  Constant time means the time, expressed in the number of steps the algorithm takes, doesn't vary based on the size of the input. The time to reach the relevant memory doesn't vary on the size of the input, but rather on the topology of your architecture. Further elements may well take less time, depending on where they're actually stored, so you can simply average out memory access to get a constant factor. 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.
- elbows 11y ago
  It takes longer to access elements that aren't in cache, but that's still a constant factor. It may be 100x or 1000x but once you're going all the way to main memory it's not going to get any worse as your array gets bigger.
- SilasX 11y ago
  I say the same thing about hashtable lookup. See this thread and the linked Reddit one[1]. 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". [1] https://news.ycombinator.com/item?id=9807739 https://news.ycombinator.com/item?id=9807739
  - TeMPOraL 11y ago
    Thanks very, very much for pointing me in the right direction! In the thread you linked, 'Cushman links[0] to a good StackExchange thread[1] that explains some related things that bothered me, and the whole thread also manages to answer my questions regarding arrays. 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 https://news.ycombinator.com/item?id=9808452 [1] - http://cs.stackexchange.com/questions/1643/how-can-we-assume-that-basic-operations-on-numbers-take-constant-time http://cs.stackexchange.com/questions/1643/how-can-we-assume...
    - vinceguidry 11y ago
- TeMPOraL 11y ago
  Replying to myself since I'm past my edit window. 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 :).

by mason55 11y ago

TeMPOraL 11y ago

I'm going to render myself permanently unemployable in the industry by admitting this, but one thing I'm still not really sure about is why every text on CS assumes array have O(1) access? I mean, in the real world it surely takes more time to reach elements further in memory, if only because electrons travel at finite speeds and also you can't magically write any number into a register, there has to be a piece of electronics that will count up to it somehow. Is it only because all those hardware operations are so stupidly fast we don't care about them day-to-day usage, or is there another reason for assuming arrays have O(1) access?

xKingfisher 11y ago
My understanding from my algorithms class is that it is simply a matter of choosing your abstraction. Big O is meant to provide a general framework for qualifying and comparing algorithms free of machine dependent factors like execution time. It is not possible to account for every possible facet of every operation so some operations are chosen to be O(1) even though in reality they take multiple machine code instructions or have slightly varying real world performance. Saying array access is O(1) also does not account for different architectures or cache misses, which have major performance implications. 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.
AnimalMuppet 11y ago
First, no, in the real world it does not take more time to reach elements further in memory. Even if the memory is physically further on a chip (and some memory has to be), the memory transfer happens on a clock edge, not just "as soon as possible", so the elements actually transfer at the same time. 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.]
- TeMPOraL 11y ago
  > Even if the memory is physically further on a chip (and some memory has to be), the memory transfer happens on a clock edge, not just "as soon as possible", so the elements actually transfer at the same time. Here is the key insight I was missing. Thank you very much!
- Terr_ 11y ago
  It'd be amusing if asynchronous processors suddenly took off and many Big-O questions became trickier.
vinceguidry 11y ago
Constant time means the time, expressed in the number of steps the algorithm takes, doesn't vary based on the size of the input. The time to reach the relevant memory doesn't vary on the size of the input, but rather on the topology of your architecture. Further elements may well take less time, depending on where they're actually stored, so you can simply average out memory access to get a constant factor. 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.
elbows 11y ago
It takes longer to access elements that aren't in cache, but that's still a constant factor. It may be 100x or 1000x but once you're going all the way to main memory it's not going to get any worse as your array gets bigger.
SilasX 11y ago
I say the same thing about hashtable lookup. See this thread and the linked Reddit one[1]. 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". [1] https://news.ycombinator.com/item?id=9807739 https://news.ycombinator.com/item?id=9807739
- TeMPOraL 11y ago
  Thanks very, very much for pointing me in the right direction! In the thread you linked, 'Cushman links[0] to a good StackExchange thread[1] that explains some related things that bothered me, and the whole thread also manages to answer my questions regarding arrays. 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 https://news.ycombinator.com/item?id=9808452 [1] - http://cs.stackexchange.com/questions/1643/how-can-we-assume-that-basic-operations-on-numbers-take-constant-time http://cs.stackexchange.com/questions/1643/how-can-we-assume...
  - vinceguidry 11y ago
TeMPOraL 11y ago
Replying to myself since I'm past my edit window. 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 :).