3 ms·
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?
by heeen2 4y ago
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?
- scatters 4y agoAmortised 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.