7 ms·
This is a very interesting article. A minor quibble - it is very difficult to find a paradigm in which the running time of the proposed algorithm differs from
by rwitts 13y ago
This is a very interesting article.
A minor quibble - it is very difficult to find a paradigm in which the running time of the proposed algorithm differs from simply choosing the best of the obvious algorithms.
Line at a time takes O( max(w,h) ). Binary searching each row and column separately takes O( min(w,h) log(max(w,h) ). Therefore, implementing both basic algorithms and using the faster one at run-time will run in time O(min(max(w,h), min(w,h)log(max(w,h)).
Which is very close to the proposed run-time - unfortunately so much so that it is very hard to find a sequence of (w,h) for which the proposed algorithm works asymptotically better than simply doing "the obvious thing".
But it is possible! And the lower bounds are nice!
- Strilanc 13y agoI (the author) actually did lose a lot of time trying to prove those weren't the same bound! Eventually I found a variable assignment that made it obvious: let w = n/log(n) let h = n (Note: I use ↑ and ↓ as binary operators for max and min.) (Note: @= means asymptotically equal. Analogous for @<.) 'switching' @= (w ↑ h) ↓ ((w ↓ h) log(w ↑ h)) @= (n/log(n) ↑ n) ↓ ((n/log(n) ↓ n) log(n/log(n) ↑ n)) @= n ↓ (n/log(n) log(n)) @= n 'lower' @= ((w ↓ h) log((w ↑ h)/(w ↓ h)) @= n/log(n) log(n/(n/log(n)) @= n log(log(n)) / log(n) @< n
- rwitts 13y agoVery nice! I'm glad that you worried about this and I have to admit that your asymptotic example is nicer than mine.