Multiple choice technology programming languages

Time complexity of algorithm1 is T (n^2) and that of algorithm2 is T (n).Then which of the following statements are true?

  1. Algorithm1 beats algorithm2 when n tends to infinity

  2. Algorithm2 beats algorithm when n tends to infinity

  3. Nothing can be said about the performance of both algorithms for lower values of n

  4. Algorithm1 performs the same as algorithm2
Reveal answer Fill a bubble to check yourself
B,C Correct answer
Explanation

Algorithm2 with T(n) time complexity is asymptotically faster than Algorithm1 with T(n^2). As n approaches infinity, n grows much slower than n^2, so Algorithm2 dominates. However, for small values of n, the constant factors hidden by Big-O notation may cause either algorithm to perform better, so nothing definitive can be said for lower n values.

Keep practicing — related questions