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 n2 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 | n2 | n3 | 2n | 3n | n! |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 2 | 3 | 1 |
| 10 | 1 | 2 | 1 | 10 | 100 | 1,000 | 1,024 | 59049 | 3.63x106 |
| 100 | 1 | 5 | 2 | 100 | 104 | 106 | 1.268x1030 | 5.15x1047 | 9.33x10157 |
| 1,000 | 1 | 7 | 3 | 103 | 106 | 109 | 1.07x10301 | ||
| 10,000 | 1 | 9 | 4 | 104 | 108 | 1012 | |||
| 100,000 | 1 | 12 | 5 | 105 | 1010 | 1015 | |||
| 1,000,000 | 1 | 14 | 6 | 106 | 1012 | 1018 | |||
| 10,000,000 | 1 | 16 | 7 | 107 | 1014 | 1021 |
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.16x107 | 3.16x1010 | 3.16x1013 |
So if you happen to pick O(n3) 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.
