3 ms·

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 m

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.