Ask Question
6 November, 15:09

Suppose you with had two algorithms, A and B, with growth functions fa (n) = 200n2 and fb (n) = 2n4. If you were to do an exact analysis on these growth functions, i. e., not simplify them with Big-Oh or tilde approximation, what algorithm would you recommend for which values of n? (Hint: you should be partitioning the domain of n > 0). Explain how you arrived at your answer and why it is correct.

+5
Answers (1)
  1. 6 November, 15:37
    0
    For values when n<32 use fb (n) else use fa (n).

    See explaination for details

    Explanation:

    Earlier when n=1 fa (n) = 2000 while fb (n) = 2. for n=2 fa (n) = 2000*22 = 2000*4=8000 while fb (n) = 2*24=2*16=32. It is observed that fa (n) requires more time than fb (n) for small values.

    Now, we will see when fb (n) crosses fa (n). This can happen only when fb (n) values equals or greater than fa (n)

    therefore,

    2000n2<=2n4

    Solving equation we get n2>=1000 which can happen when n>=32.

    So for values when n<32 use fb (n) else use fa (n)
Know the Answer?
Not Sure About the Answer?
Find an answer to your question ✅ “Suppose you with had two algorithms, A and B, with growth functions fa (n) = 200n2 and fb (n) = 2n4. If you were to do an exact analysis on ...” 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