Ask Question
16 June, 18:15

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)

+1
Answers (1)
  1. 16 June, 19:24
    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 and Technology if you're in doubt about the correctness of the answers or there's no answer, then try to use the smart search and find answers to the similar questions.
Search for Other Answers