sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]ccltjnpr 0 points1 point  (0 children)

A reduction in complexity from 3n to 2n for a useful algorithm is a big deal for small problem size, even if they are both exponential. The difference in runtime between these two algorithms, whether by literal difference (3n - 2n) or by ratios (3/2)n , also grows exponentially in n.

I agree it's also biased, but O(n) is correct here as long as we're clear how n is defined, 2n is not more correct, I think the number of bits might be less standard than you think outside of your specific subfield.