Question

Suppose for the worst case, given input size n: Algorithm 1 performs f(n) = n2 + n/2 steps Algorithm 2 performs f(n) = 12n + 500 steps What is the smallest value of n for which algorithm 2 will be faster than algorithm 1?

Answer 1

Answer:

29

Explanation:

for n=28:

--------------

Algorithm 1 performs f(n) = n2 + n/2 = 28*28 + 28/2 = 798

Algorithm 2 performs f(n) = 12*28 + 500 = 836

for n=29

--------------

Algorithm 1 performs f(n) = n2 + n/2 = 29*29 + 29/2 = 855.5

Algorithm 2 performs f(n) = 12*29 + 500 = 848

so, for n=29, algorithm 2 will be faster than algorithm 1