Read twice please, complete and full answer in order to give credit,thanks Suppo

Question

Read twice please, complete and full answer in order to give credit,thanks

Suppose you implemented a quadratic time (that is O(n 2 )) algorithm for a problem P. On a test run, your algorithm takes 50 seconds on inputs of size 1000. Your friend found a clever algorithm which solves the same problem with a running time O(n 3/2 ). However, the faster algorithm takes 150 seconds on inputs of size 1000. How could this be? If you need to solve a problem of size 4000, which algorithm you should use? What about inputs of size 10,000? Explain your answers (assume low-order terms are negligible).

Explanation / Answer

O(n) or big-oh(n) is defined only for larger input or we can say it will work only for larger input.

In the given question, size is 1000 which is not very large. Hence, O(n3/2) may perform worst than O(n2) for smaller size input. But if size is 10,000 which is significanlty large O(n3/2) will perform better than O(n2) algorithm.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.