undefined | Better HN

0 pointsheeen23y ago0 comments

doesn't that still depend on the length of the input string? If I feed it a billion 9s it still has to look at all of them. Am I missing an obvious shortcut?

0 comments

scatters3y ago

Amortised constant is over all inputs, and almost all natural numbers are not 1 less than a power of 10.

Of course, you need to start at the correct end, otherwise it's logarithmic just to get there.

j / k navigate · click thread line to collapse

0 comments

scatters3y ago

Amortised constant is over all inputs, and almost all natural numbers are not 1 less than a power of 10.

Of course, you need to start at the correct end, otherwise it's logarithmic just to get there.

j / k navigate · click thread line to collapse