# Algorithm Performance

I was chatting to a colleague recently who although he was a very good programmer, did not have a computer science/maths background – this was fine until he wanted to use bubble sort on a large(ish) (100k) number of records and I had to explain to him about how algorithms that take n^{2} time are not your friend for big (or even little) n.

One of the most important decisions you can make when optimizing an application is the up-front choice of algorithm to use, performance tuning and optimization can make a difference but you are very lucky to achieve 2x-5x improvement, to be able to make 10x or 100x improvement in your application you need decent algorithm choice.

Here’s a little table I put together to help explain why you have to be careful and know the time/space performance of any algorithm you put in your applications.

Items | const | ln n | log n | n | n^{2} |
n^{3} |
2^{n} |
3^{n} |
n! |
---|---|---|---|---|---|---|---|---|---|

1 | 1 | 0 | 0 | 1 | 1 | 1 | 2 | 3 | 1 |

10 | 1 | 2 | 1 | 10 | 100 | 1,000 | 1,024 | 59049 | 3.63x10^{6} |

100 | 1 | 5 | 2 | 100 | 10^{4} |
10^{6} |
1.268x10^{30} |
5.15x10^{47} |
9.33x10^{157} |

1,000 | 1 | 7 | 3 | 10^{3} |
10^{6} |
10^{9} |
1.07x10^{301} |
||

10,000 | 1 | 9 | 4 | 10^{4} |
10^{8} |
10^{12} |
|||

100,000 | 1 | 12 | 5 | 10^{5} |
10^{10} |
10^{15} |
|||

1,000,000 | 1 | 14 | 6 | 10^{6} |
10^{12} |
10^{18} |
|||

10,000,000 | 1 | 16 | 7 | 10^{7} |
10^{14} |
10^{21} |

Now is this the approximate time/space growth you will get; how long your process will take will depend on the cost of each operation and to give you a guide, here’s now many units there are in one year.

Seconds | Milliseconds | Microseconds | |
---|---|---|---|

1 year | 3.16x10^{7} |
3.16x10^{10} |
3.16x10^{13} |

So if you happen to pick O(n^{3}) algorithm you are going to have to waiting between 16 minutes and around 35 years to solve for just a 1,000 items!

Notice also that as the notation power grows, even micro-second execution times (or expanding onto Cloud infrastructure) isn’t going to help too much.