# Uber ETA - System Design Newsletter

Posted

Uber ETA - System Design Newsletter by Neo Kim.

Dijkstra’s algorithm is known for finding the shortest path in a graph.

But the time complexity of Dijkstra’s algorithm is O(n logn). And

nis the number of road intersections or nodes in the graph.San Francisco Bay Area alone has half a million road intersections. So Dijkstra’s algorithm is not enough at Uber’s scale.

So theypartitionedthe graph. And thenprecomputedthe best path within each partition.