6 ms·

> O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. Argh, I hate this every time I s

> O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. Argh, I hate this every time I see Big O notation covered. Big O != performance. If you have an O(N) algorithm that walks the data set in the order that it's laid out in memory(assuming contiguous data) it will beat your O(NlogN) and sometimes even O(logN). [edit]meant to omit nlogn, that's what I get for any early morning rant pre-coffee. Radix Sort is the classic example I always bring up. On machine word size keys, with a separate pointer look-up table(to get final value) it will beat QSort, MergeSort and all the other NlogN sorts by 10-50x. This includes having to walk the data 3-4 times depending on how you want to split the radix to line up with cache sizes. Friends don't let Friends use Big O to describe absolute performance.

dominotw 11y ago
>By one estimate, the health care costs of obesity are responsible for nearly 21 percent of total health care spending in the U.S. BigO has nothing to do with performance even though that what we most use it for. Its simply a classification of growth characteristics, relationship between two functions.
- deleted 11y ago
  [deleted]
castratikron 11y ago
Of course an O(N) method will beat an O(NlgN) method, because O(N) < O(NlgN). Radix sort is a linear time sort because the hardware (random access memory) is built to allow constant-time lookup of memory. Radix sort wouldn't be linear time on a sequential access memory system, like tape, but merge sort would still be O(NlgN) on such a system.
- hnkain 11y ago
  It doesn't invalidate what you say, but you're assuming there's a bounded number of different values in the array -- 2^k where k is your word size. Under this assumption, a correctly implemented quicksort also runs in O(N) time.
decebalus1 11y ago
> If you have an O(N) algorithm that walks the data set in the order that it's laid out in memory(assuming contiguous data) it will beat your O(NlogN) Not sure what you're trying to say with this particular statement. Of course it will. NLogN grows way faster than N. And Radix sort is of course drastically faster than comparison sorts if the word size is smaller than logN regardless of the particularities of the implementation. People don't and shouldn't use big O to describe absolute performance but it's a great place to start and you can't reach the level of implementation details performance tuning if you can't understand or formalize the basics. But you do have a point overall. In practice, performance may be different. Big O assumes a particular 'virtual machine' with a particular word size and a particular time it takes to execute an instruction.
- vvanders 11y ago
  Yeah, meant to omit NlogN there, I blame it on lack of coffee. My meta point is the constant factors that Big O throws out usually end up dominating real-world performance.
  - copperx 11y ago
    That's why some Data Stuctures courses use tilde notation instead (same as big O, but the constant is preserved).
- Rhapso 11y ago
  In big-O senses Radix sort is one of those more persistent misconceptions. At scale Radix sort has to be nlog(n) because you should really consider the possibility all your numbers are unique. This does not even start on the reality that memory access really is O(n^(1/3)), addition is O(n) and a lot of other things we assume are O(1) are not.
bojank 11y ago
When talking about theory, I have two points: - First: O(N) < O(N log N), so your example isn't good - Second: Your description of Radix sort is actually O(N), and the standard sorting algorithms are O(N log N), so it again isn't a surprise, theoretically speaking... The thing that Big-O knowingly hides is the constant factor. For example, some algorithms are 2N and some are 1000N. For large enough N, this may not matter, but for any reasonably sized N, it does. In practice, of course that Big-O is not sufficient to describe absolute algorithm performance, as it depends on so many factors such as implementation, computer architecture, relative size of data, etc. But, when looking at an algorithm and knowing its Big-O complexity can often be a useful input to your decision on whether to use it. So I disagree with this Big-O bashing...
- deleted 11y ago
  [deleted]
umanwizard 11y ago
The statement you quoted is correct. It doesn't say "O(log(N)) algorithms are faster than O(N) algorithms." It says performance of a particular algorithm degrades linearly as data set grows, if that algorithm is O(N). Which is true. (asymptotically)
- vvanders 11y ago
  I was nitpicking the performance part of the statement. N does scale linearly. The point I was trying(and failed) to drive home is that it matters how you walk your N not just what the N is. If you've got to do a pointer indirection for each N rather than a linear read that can end up dominating the non-constant factors in a lot of cases.
  - umanwizard 11y ago
    You're not understanding what I'm saying. It's of course true that some O(N) algorithms are slower than other O(N) algorithms. But the statement you quote doesn't imply the contrary. Obviously walking an array can be thousands of times faster than walking a linked list. That doesn't change the fact that walking an array of size 3*N is 3 times slower than walking an array of size N, which is (roughly) what big-O notation means and what the quote you're objecting to correctly claims. > If you've got to do a pointer indirection for each N rather than a linear read that can end up dominating the non-constant factors in a lot of cases. Huh? Pointer indirection and cache miss for each element is already non-constant (you have to do it N times) so I don't understand what it means that this "can end up dominating the non-constant factors".
    - vvanders 11y ago
      Not really. Take the linked-list case for example. Let's say the allocator you have is a small-block allocator, of which most good malloc implementations use for linked-list style allocations. Since the SBA allocates in chunks your cache locality(driving your "constant-factor" performace) isn't linear any more. It'll change in jumps & starts as you break chunk boundraries. Also another class allocating in-between your linked list allocations(really common) will break up the chunk locality and now your real-world O(N) performance no longer scales linearly.
TillE 11y ago
You're overlooking the word "grow". There's nothing wrong with that sentence. No absolutes.

dominotw 11y ago

>By one estimate, the health care costs of obesity are responsible for nearly 21 percent of total health care spending in the U.S. BigO has nothing to do with performance even though that what we most use it for. Its simply a classification of growth characteristics, relationship between two functions.

deleted 11y ago
[deleted]

castratikron 11y ago

Of course an O(N) method will beat an O(NlgN) method, because O(N) < O(NlgN). Radix sort is a linear time sort because the hardware (random access memory) is built to allow constant-time lookup of memory. Radix sort wouldn't be linear time on a sequential access memory system, like tape, but merge sort would still be O(NlgN) on such a system.

hnkain 11y ago
It doesn't invalidate what you say, but you're assuming there's a bounded number of different values in the array -- 2^k where k is your word size. Under this assumption, a correctly implemented quicksort also runs in O(N) time.

decebalus1 11y ago

> If you have an O(N) algorithm that walks the data set in the order that it's laid out in memory(assuming contiguous data) it will beat your O(NlogN) Not sure what you're trying to say with this particular statement. Of course it will. NLogN grows way faster than N. And Radix sort is of course drastically faster than comparison sorts if the word size is smaller than logN regardless of the particularities of the implementation. People don't and shouldn't use big O to describe absolute performance but it's a great place to start and you can't reach the level of implementation details performance tuning if you can't understand or formalize the basics. But you do have a point overall. In practice, performance may be different. Big O assumes a particular 'virtual machine' with a particular word size and a particular time it takes to execute an instruction.

vvanders 11y ago
Yeah, meant to omit NlogN there, I blame it on lack of coffee. My meta point is the constant factors that Big O throws out usually end up dominating real-world performance.
- copperx 11y ago
  That's why some Data Stuctures courses use tilde notation instead (same as big O, but the constant is preserved).
Rhapso 11y ago
In big-O senses Radix sort is one of those more persistent misconceptions. At scale Radix sort has to be nlog(n) because you should really consider the possibility all your numbers are unique. This does not even start on the reality that memory access really is O(n^(1/3)), addition is O(n) and a lot of other things we assume are O(1) are not.

bojank 11y ago

When talking about theory, I have two points: - First: O(N) < O(N log N), so your example isn't good - Second: Your description of Radix sort is actually O(N), and the standard sorting algorithms are O(N log N), so it again isn't a surprise, theoretically speaking... The thing that Big-O knowingly hides is the constant factor. For example, some algorithms are 2N and some are 1000N. For large enough N, this may not matter, but for any reasonably sized N, it does. In practice, of course that Big-O is not sufficient to describe absolute algorithm performance, as it depends on so many factors such as implementation, computer architecture, relative size of data, etc. But, when looking at an algorithm and knowing its Big-O complexity can often be a useful input to your decision on whether to use it. So I disagree with this Big-O bashing...

deleted 11y ago
[deleted]

umanwizard 11y ago

The statement you quoted is correct. It doesn't say "O(log(N)) algorithms are faster than O(N) algorithms." It says performance of a particular algorithm degrades linearly as data set grows, if that algorithm is O(N). Which is true. (asymptotically)

vvanders 11y ago
I was nitpicking the performance part of the statement. N does scale linearly. The point I was trying(and failed) to drive home is that it matters how you walk your N not just what the N is. If you've got to do a pointer indirection for each N rather than a linear read that can end up dominating the non-constant factors in a lot of cases.
- umanwizard 11y ago
  You're not understanding what I'm saying. It's of course true that some O(N) algorithms are slower than other O(N) algorithms. But the statement you quote doesn't imply the contrary. Obviously walking an array can be thousands of times faster than walking a linked list. That doesn't change the fact that walking an array of size 3*N is 3 times slower than walking an array of size N, which is (roughly) what big-O notation means and what the quote you're objecting to correctly claims. > If you've got to do a pointer indirection for each N rather than a linear read that can end up dominating the non-constant factors in a lot of cases. Huh? Pointer indirection and cache miss for each element is already non-constant (you have to do it N times) so I don't understand what it means that this "can end up dominating the non-constant factors".
  - vvanders 11y ago
    Not really. Take the linked-list case for example. Let's say the allocator you have is a small-block allocator, of which most good malloc implementations use for linked-list style allocations. Since the SBA allocates in chunks your cache locality(driving your "constant-factor" performace) isn't linear any more. It'll change in jumps & starts as you break chunk boundraries. Also another class allocating in-between your linked list allocations(really common) will break up the chunk locality and now your real-world O(N) performance no longer scales linearly.

TillE 11y ago

You're overlooking the word "grow". There's nothing wrong with that sentence. No absolutes.