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?
undefined subscriptions will be displayed on your profile (edit)
Skip for now
For your security, we need to re-authenticate you.
Click the link we sent to , or click here to sign in.
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?