Algorithm Performance
 Posted in:
 Algorithms
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 upfront choice of algorithm to use, performance tuning and optimization can make a difference but you are very lucky to achieve 2x5x 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 microsecond execution times (or expanding onto Cloud infrastructure) isn’t going to help too much.