On: Why we need SIMD

[DarkNova6]

Big O Notation omis constant factors that tend to be significantly larger for log-n algorithms.

I think he talked from personal experience.

[f1shy → DarkNova6]

Could be. But very poorly stated if so.

Anyway, I do not think that even "typically" such statement can remotely be truth. It is 2 orders of magnitude away (20 to 5000).

[DarkNova6 → f1shy]

True, but it wouldn’t be unthinkable. Especially if the O(n) algorithm accesses data sequentially and the O(log n) has indirections.

But maybe the author simply made it up.

[corysama → DarkNova6]

You are all right. I was wrong. Should not post math just before going to sleep… So, let’s make the same mistake first thing in the morning:

x=20log2(x) at 143

https://www.wolframalpha.com/input?i=x%3D20*log2%28x%29