undefined | Better HN

0 pointsccapitalK5mo ago0 comments

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?

0 comments

DarkNova65mo ago

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

I think he talked from personal experience.

f1shy5mo ago

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).

DarkNova65mo ago

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.

1 more reply

j / k navigate · click thread line to collapse

0 pointsccapitalK5mo ago0 comments

0 comments

DarkNova65mo ago

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

I think he talked from personal experience.

f1shy5mo ago

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).

DarkNova65mo ago

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.

1 more reply

j / k navigate · click thread line to collapse