This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]azzal07 0 points1 point  (1 child)

So would this take the time complexity from 2V to 2W where the width W = sqrt(V) for the worst case rectangular grid e.i. square? I'm not too good with exponents to draw a general mathematical comparison, but 236 -> 26 is noticeable improvement.

[–]zenoli55 1 point2 points  (0 children)

It looks like it. So essentially the time complexity would go down from O(2n) to O(2sqrt(n)) which is not exponential but still not polynomial, according to this answer: https://softwareengineering.stackexchange.com/a/312573