5 ms·

For those who aren't getting anonymoushn's point - outputting a O(n) bytes will take O(n) time, no matter if your processing per piece of output is fast or slow

by azernik 15y ago

For those who aren't getting anonymoushn's point - outputting a O(n) bytes will take O(n) time, no matter if your processing per piece of output is fast or slow. In fact, this optimization will only give constant-time speedup from an iterative or functional solution - those do some (very cheap) numerical operations for every number in the range, while this does (even cheaper) array lookup for 7 out of every 15 numbers. A decent-sized constant-factor speedup is still only a constant-factor speedup.

jbri 15y ago
That assumes you're providing the output as a list of elements. Since it's a contiguous sequence, you can uniquely identify a particular output as a tuple (start, length). So you can get a constant-time solution if you're allowed to assume the input is valid (and have a constant-time way of getting the length of the input, I guess). On the other hand, checking to ensure that the input represents a valid sequence is going to be O(n) in the size of the input no matter what you do...