Complete and correct answer in order to give full creditthan

Complete and correct answer in order to give full credit,thank you

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

Solution

May be because of lower order terms and constants like value of C O(n 3/2) might take more time for small input.

For a problem of size 4000, depending on the value of n0, we will look ahead to use any of the given algorithms. Like quick sort runs faster than insertion sort but for small value of n and sorted data, insertion sort runs over quick sort.

In the similar fashion, same method can be applied here as well. It may be possible the algorithm which take O(n^2) may run faster for several pattern of inputs or for small range of n but for larger value of n, we must go for effiecient algo. O(n 3/2) (in this case).