ETA requests doesn't need to consider entire X, it could be much smaller numbers, for more than 99% requests x would be 1 which means they are within a city, only 1% would be multicity where x>1 I am assuming, even in that case x would be still very small.
Okay suppose whole world is made of X San Francisco Bay areas which has Y road intersections.
So total nodes across the world map = X * Y
1. Without partitioning dijkstra time complexity of order (X*Y) log (X*Y)
2. With partitioning i am interacting with boundary nodes only for each partition.
So now, number of boundary nodes per partition = Y ^ 1/2 (as going area to perimeter)
and effective time complexity becomes of order (X * Y^1/2) log(X * Y^1/2)
Just to give an idea, lets take X = 10K, Y = 500, 000 (half million)
1. without paritioning time complexity of order ~ 5e9 (5 * 10 ^ 9)
2. with partitioning time complexity of order ~ 7e6
Doesn't sound much of an optimization assuming X can be very large as we are talking about the world here
Am i missing something here?
ETA requests doesn't need to consider entire X, it could be much smaller numbers, for more than 99% requests x would be 1 which means they are within a city, only 1% would be multicity where x>1 I am assuming, even in that case x would be still very small.