To make it a fair comparison, I think that it's necessary to correct the time considering that the amoeba is computing in parallel, at lest in the N channels that are useful, and perhaps in the N^2 channels that connect all the cities. So it's more accurate to compare this with an algorithm that is O(N^3) in a normal classic sequential computer.