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...
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.
My meta point is the constant factors that Big O throws out usually end up dominating real-world performance.
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.
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.
> 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".
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.
There's nothing wrong with that sentence. No absolutes.
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.
Under this assumption, a correctly implemented quicksort also runs in O(N) time.
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.
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.