3 ms·
I've seen two recent posts that mention 'exponentially faster '. Does this have a precise meaning? I could imagine it to mean making a non-exponential algorithm
by karmakaze 8y ago
I've seen two recent posts that mention 'exponentially faster '. Does this have a precise meaning? I could imagine it to mean making a non-exponential algorithm for a problem which only had exponential ones. Another interpretation could be making an algorithm with 2^n steps where previous ones took 2^(2n) steps making the improvement factor 2^n, but still resulting in an exponential time algorithm. Should we just accept this a la 'literally'.
- yorwba 8y agoAccording to this StackExchange answer https://cs.stackexchange.com/a/50356 https://cs.stackexchange.com/a/50356 the speedup is best expressed as a function relating the two algorithm's run times. So if there's a constant factor of 2, then that's "twice as fast", but if the relationship isn't linear (e.g. 2^(2n) = (2^n)^2 is a quadratic function of 2^n) then the speedup is named correspondingly. So 2^(2n) -> 2^n is quadratic speedup, while 2^n -> n or n -> log n are exponential speedups.
- allenz 8y agoIn this case, exponentially faster means that the parallel running time improved from O(n) to O(log n).