[Introduction to Algorithms, CLRS] Problems 1.1
This is a solution for Introduction to Algorithms. I write this for my study purpose.
Problems 1-1 Comparison of running times
For each function f .n/ and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f .n/ microseconds.
Answer:
We assume a 30 day month and 365 day year. I use '^' for 'to the'.
|
1 second |
1 minute |
1 hour |
1 day |
1 month |
1 year |
1 century |
lg n |
2^(10^6) |
2^(6*(10^7)) |
2^(3.6*(10^9)) |
2^(8.64*(10^10)) |
2^(2.592*(10^12)) |
2^(3.1536*(10^13)) |
2^(3.15576*(10^15)) |
sqrt(n) |
1*(10^12) |
3.6*(10^15) |
1.29*(10^19) |
7.46*(10^21) |
6.72*(10^24) |
9.95*(10^26) |
9.96*(10^30) |
n |
1*(10^6) |
6*(10^7) |
3.6*(10^9) |
8.64*(10^10) |
2.59*(10^12) |
3.15*(10^13) |
3.16*(10^15) |
n lg n |
189481 |
8.64*(10^6) |
4.18*(10^8) |
8.69*(10^9) |
2.28*(10^11) |
2.54*(10^12) |
2.2*(10^14) |
n^2 |
1000 |
7745 |
60000 |
293938 |
1609968 |
5615692 |
56176151 |
n^3 |
100 |
391 |
1532 |
4420 |
13736 |
31593 |
146679 |
2^n |
19 |
25 |
31 |
36 |
41 |
44 |
51 |
n! |
9 |
11 |
12 |
13 |
15 |
16 |
17 |
source: http://sites.math.rutgers.edu/~ajl213/CLRS/Ch1.pdf