0 Comments

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

n2

n3

2n

3n

n!

1

100111231

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

 SecondsMillisecondsMicroseconds
1 year3.16x1073.16x10103.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.