2 ms·
This often trips up people who don't know how big O works (loops are not directly correlated to N), or why it works that way (in general a constant before N is
by zamalek 8y ago
This often trips up people who don't know how big O works (loops are not directly correlated to N), or why it works that way (in general a constant before N is negligible, the curve is more interesting).
This single pass approach introduces a conditional branch inside a loop, which I've found to be generally slower on x86 - because I've made that mistake and years later found a huge performance benefit by using the "dumb" (multiple loop) approach.
- tralarpa 8y ago> This often trips up people who don't know how big O works They didn't ask for an algorithm with linear complexity. They explicitly asked for a solution "in one pass". That's highly misleading. Edit (after the reply by zamalek): And you are perfectly right about the performance: it's probably slower than just doing two passes (one to find the length, the second to find the middle).
- zamalek 8y agoAs the root comment points out, both solutions (the second being two loops) are 1.5 passes.