2 ms·
I'm sure you're right in this case, but I wonder if it would be possible for an 'optimal' algorithm, where the optimality is in terms of high-level operations l
by chrisseaton 10y ago
I'm sure you're right in this case, but I wonder if it would be possible for an 'optimal' algorithm, where the optimality is in terms of high-level operations like compares required, to be out-performed by a non-optimal algorithm due to practical considerations such as cache utilisation. An order of magnitude more loads but in a cache oblivious pattern could be a win compared to a pathological pattern.
- mcguire 10y agoCertainly. Jon Bentley had an article on two string reversal algorithms with the same algorithmic complexity. On a very large string, one would finish almost immediately; the other was pessimal for paged virtual memory and wouldn't finish for hours.