4 ms·

> Your general point is still right in that an O(n*log(n)) algorithm is not necessarily slower than an O(n) algorithm in practice. Sounds reasonable > for a s

> Your general point is still right in that an O(n*log(n)) algorithm is not necessarily slower than an O(n) algorithm in practice. Sounds reasonable > for a small N of 10000 Ah, now that is not what I would call a small N

tialaramex 3y ago
10_000 is easily in the ballpark of constant factors k which really happen in software. Suppose my O(n) algorithm is a random access walk of nums. So I'm causing ~10_000 memory fetches, maybe they each take k=100 cycles, so it takes 1 million cycles total. But the O(n*log(n)) algorithm happens to be linear, it does access some nearby objects more than once, but every damn access is in cache. That's only 100_000 cycles, it's ten times faster despite you not thinking 10000 is a small N. Stalls are huge. A modern CPU can do a crazy amount of arithmetic in the time it takes to fetch from even an L3 shared cache, never mind main memory. If you need to go out, to the network or to "disk" it starts to look faster to do a whole bunch of difficult work again instead. Oh the 2417th digit of Pi is on the hard disk? Thanks but I'll just calculate it again instead 'cos I don't got all day.
- _a_a_a_ 3y ago
  Thank you for the lesson in memory access times I actually know something about the subject already :-) > But the O(n*log(n)) algorithm I think you're badly missing out the "* log(n)" part. But on reflection, you have made your point, thank you.
  - tialaramex 3y ago
    > I think you're badly missing out the "* log(n)" part. Nope? But I can see why you might have missed it, instinctively log(10_000) feels like it should be pretty big. It feels big, doesn't it. Not as big as n, but surely a sizeable quantity. However the log to base 2 (which we might decide we prefer to care about here since this is computer science) is about 13. So yeah, the numbers work out fine. I guess it's possible my use of the word "linear" confused you. I'm talking linear in comparison to random access, not suggesting that somehow a log-linear complexity is the same as a linear complexity. But then, you know "something" about this so maybe not. EtA: Aha, I realised my mistake, I just used rough numbers, maybe you'd have realised if I'd written 132 870 cycles or something even though that's obviously not correct because it's excessive accuracy.
aidenn0 3y ago
If you pick base 2 for the then log2(10000) is about 13. So if you are a constant factor of >13 faster for the work that dominates, the n*log(n) will be faster. Slightly OT: I remember in my algorithms class we used to joke that log(log(N)) was the same as a constant factor of 5 (in the 64-bit era, perhaps we should say 6).

tialaramex 3y ago

10_000 is easily in the ballpark of constant factors k which really happen in software. Suppose my O(n) algorithm is a random access walk of nums. So I'm causing ~10_000 memory fetches, maybe they each take k=100 cycles, so it takes 1 million cycles total. But the O(n*log(n)) algorithm happens to be linear, it does access some nearby objects more than once, but every damn access is in cache. That's only 100_000 cycles, it's ten times faster despite you not thinking 10000 is a small N. Stalls are huge. A modern CPU can do a crazy amount of arithmetic in the time it takes to fetch from even an L3 shared cache, never mind main memory. If you need to go out, to the network or to "disk" it starts to look faster to do a whole bunch of difficult work again instead. Oh the 2417th digit of Pi is on the hard disk? Thanks but I'll just calculate it again instead 'cos I don't got all day.

_a_a_a_ 3y ago
Thank you for the lesson in memory access times I actually know something about the subject already :-) > But the O(n*log(n)) algorithm I think you're badly missing out the "* log(n)" part. But on reflection, you have made your point, thank you.
- tialaramex 3y ago
  > I think you're badly missing out the "* log(n)" part. Nope? But I can see why you might have missed it, instinctively log(10_000) feels like it should be pretty big. It feels big, doesn't it. Not as big as n, but surely a sizeable quantity. However the log to base 2 (which we might decide we prefer to care about here since this is computer science) is about 13. So yeah, the numbers work out fine. I guess it's possible my use of the word "linear" confused you. I'm talking linear in comparison to random access, not suggesting that somehow a log-linear complexity is the same as a linear complexity. But then, you know "something" about this so maybe not. EtA: Aha, I realised my mistake, I just used rough numbers, maybe you'd have realised if I'd written 132 870 cycles or something even though that's obviously not correct because it's excessive accuracy.

aidenn0 3y ago

If you pick base 2 for the then log2(10000) is about 13. So if you are a constant factor of >13 faster for the work that dominates, the n*log(n) will be faster. Slightly OT: I remember in my algorithms class we used to joke that log(log(N)) was the same as a constant factor of 5 (in the 64-bit era, perhaps we should say 6).