4 ms·
Am I getting the math wrong here? Going from O(n) to O(log n) (with no change in constant factor) for a million items would be going from ~1000000c ops to ~20c
by ccapitalK 1y ago
Am I getting the math wrong here? Going from O(n) to O(log n) (with no change in constant factor) for a million items would be going from ~1000000c ops to ~20c ops, which would be a 50000x improvement?
- DarkNova6 1y agoBig O Notation omis constant factors that tend to be significantly larger for log-n algorithms. I think he talked from personal experience.
- f1shy 1y agoCould 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 1y agoTrue, 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 1y agoYou 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 https://www.wolframalpha.com/input?i=x%3D20*log2%28x%29