Algorithms: Running times

Processing time to solve any computational problem on any hardware is limited, so the efficiency of the algorithm mapping input to output makes all the difference. So, if the running time of an algorithm f(n), grows in proportion and relative to the input size, is log n(base 2) in microseconds, how much of an input can it handle in 1 second. In 1 microsecond it can handle an input size of 2,so in 1 second(1 second = 1000000 microseconds), it can handle and input size of  2000000.

Comparing this algorithm to the running time of a very slow algorithms f(n) which takes n! microseconds, it can handle an input size of about 9.

Here is a comparison of the efficiency of algorithms with different running times.

microseconds

1s

1m

1h

1d

1 month

1 year

1 century

log2n

2000000

120000000

7200000000

172800000000

5184000000000

62208000000000

6220800000000000

√n

2000000

120000000

7200000000

172800000000

5184000000000

62208000000000

6220800000000000

n

1000000

60000000

3600000000

86400000000

2592000000000

31104000000000

3110400000000000

n log2n

500000

30000000

1800000000

43200000000

1296000000000

15552000000000

1555200000000000

n2

1000

60000

3600000

86400000

2592000000

31104000000

3110400000000

n3

100

6000

360000

8640000

259200000

3110400000

311040000000

2n

20

1200

72000

1728000

51840000

622080000

62208000000

n!

9

540

32400

777600

23328000

279936000

27993600000

Leave a Reply

Your email address will not be published. Required fields are marked *