Question

An algorithm takes 1 second for input size 10. Estimate the number of seconds the algorithm would require on the same computer when the input size doubles (20), triples (30), and quadruples (40) if its running time is each of the following:
O(log n), O(log^2 n), O(n), O(n log n), O(n^2), O(n^2 log^2 n), O(n^3), O(2^n), O(n^n)

Answer 1

Answer with Explanation:

O(1) for N = 10 is  1 seg, to estimate the others we need to solve the operations inside the parentheses keeping in mind the result for O(1):

For N = 10

• O(log n) = 1 seg
• O(log^2 n) = 3.3 seg
• O(n) is equal to O(1) for N = 10 therefore, O(n) = 1 seg
• O(n log n) is equal to O(1) for N = 10 by O(log n) therefore,  O(n log n) = 3.3 seg
• O(n^2 log^2 n) is 10 times greater than O(n log n) therefore, O(n^2 log^2 n) = 33 seg
• O(n^3) is 100 times greater than O(n) therefore, O(n^3) = 100 seg

• O(2^n) = 102.4 seg
• O(n^n) = 1000000000 seg

Similar for N = 20

• O(log n) = 1.3 seg
• O(log^2 n) = 4.32 seg
• O(n) = 2 seg
• O(n^2 log^2 n) = 43.2 seg
• O(n^3) = 800 seg

• O(2^n) = 104857.6 seg
• O(n^n) = 10^25 seg

for N = 40

• O(log n) = 1.47 seg
• O(log^2 n) = 4.32 seg
• O(n) = 4 seg
• O(n^2 log^2 n) = 851 seg
• O(n^3) = 6400 seg

• O(2^n) = 1.1*10^11 seg
• O(n^n) = 1.2*10^63 seg