Question

1. Suppose you are given 3 algorithms A1, A2 and A3 solving the same problem. You know that in the worst case the running times are T1(n) = (10^4)n, T2(n) = 10n , T3(n) = (10^3)(n^3) log10 n (a) Which algorithm is the fastest for very large inputs? Which algorithm is the slowest for very large inputs? (Justify your answer.) (b) For which problem sizes is A1 the best algorithm to use (out of the three)? Answer the same question for A2 and then for A3. (Justify your answer.)

Answer 1

T1(n) = (10^4)n, T2(n) = 10ⁿ , T3(n) = (10^3)(n^3) log10 n


A)

Which algorithm is the fastest for very large inputs?
A1 is fastest for large Input, because T1 takes linear time to solve the problem
A2 is slowest for large input , Its because growth rate of exponential is much higher than that of polynomial.

B)

A1 is better for values greater than 4 since the grown for A1 is linear

A2 is better for values less than equal to 4 and greater than equal to 1 , since T2 = 10⁴ and T1 = 4*10^4

A3 is better only for value n = 0 since log₁₀ 1 is 0 and T2(1) = 1 AND T3 = 0

Thanks, PLEASE COMMENT if there is any concern.