'Jeff Dean':http://research.google.com/people/jeff/ , a famous Google engineer, popularized a list of latency 'numbers everyone should know':http://highscalability.com/numbers-everyone-should-know. The list is a great resource for designing large scale infrastructure systems.

*sidenote* 'Jeff Dean':http://research.google.com/people/jeff/ , a famous Google engineer, popularized a list of latency 'numbers everyone should know':http://highscalability.com/numbers-everyone-should-know. The list is a great resource for designing large scale infrastructure systems.

Algorithms and their complexity often occur in critical parts of computer systems, but I find that few engineers have a good understanding of how a O(n!) algorithm compares to a O(n^5^) one.

These numbers aren't very precise, they assume in memory operations and some varying constant factors, but they do give a good starting point in your search for a solution that fits your problem and your data size.

Let's go through an example. Suppose you work for a GPS company and your project is to improve their directions feature. In school you've learned about using Dijkstra's algorithm to find the shortest path between two nodes in a graph. Knowing these numbers you will understand that it will take seconds to process a graph with millions of edges given that Dijkstra implementations have m log n time complexity (where m is the number of edges and n the number of nodes).

Let's go through an example.
 
Suppose you work for a GPS company and your project is to improve their directions feature. In school you've learned about using Dijkstra's algorithm to find the shortest path between two nodes in a graph. Knowing these numbers you will understand that it will take seconds to process a graph with millions of edges given that Dijkstra implementations have m log n time complexity (where m is the number of edges and n the number of nodes).

Now you face a few questions:
How fast do you want your code to be? seconds? hundreds of milliseconds?

Usually people feel something on the web is fast if it takes less then half a second to execute. So let's say half a second.

A response on the web feels fast if it takes less then 500 milliseconds. So let's pick half a second.

How big is your graph? Do you want to solve the problem for a city, a coutry or even a continent?

How big is the graph? Do you want to solve the problem for a city, a coutry or even a continent?

Each is about a magnitude larger than the other and may mean you need different approaches. Let's say we want to solve it for the whole of Europe.

Each is about a magnitude larger than the other and will be solved by different approaches. Let's say we want to solve the problem for the whole of Europe.

Here are sizes for a few input sets:

| #directed edges | 42 199 587 | 47 244 849 | 58 213 192 |
| #road categories | 13 | 13 | 4 |

Since we chose half a second to be our execution time and the size of our problem to be about 20 million edges it's clear from our table that m log n is too slow. So pure Dijkstra won't do. We need to look at how other algorithms like A star search or one based on 'Highway hierarchies':http://algo2.iti.kit.edu/schultes/hwy/esa06HwyHierarchies.pdf behave for this problem.

Since we chose half a second to be our execution time and the size of our problem to be about 40 million edges it's clear from our table that m log n is too slow. So pure Dijkstra won't do. We need to look at how other algorithms like A star search or one based on 'Highway hierarchies':http://algo2.iti.kit.edu/schultes/hwy/esa06HwyHierarchies.pdf behave for this problem.

public

protected