Ask 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)

+5
Answers (1)
  1. 14 June, 06:55
    0
    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
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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 ...” in 📗 Computers & Technology if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers