Multiple choice

Consider the following functions f1(n) and f2(n) f1(n) = n3 for 0 ≤ n < 10,000 n2 for n ≥ 1 f2(n) = n for 0 ≤ 100 n2 for n ≥ 10,000. Which of the following is true?

  1. f1(n) is O(f2(n))

  2. f1(n) is O(n3)

  3. f2(n) is O(f1(n))

  4. f1(n) is O(n)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

For large n, f1(n) behaves like n^2 and f2(n) behaves like n^2. Since they grow at the same rate asymptotically, f1(n) is O(f2(n)) and vice versa. However, f1(n) is definitely O(n^3).

Keep practicing — related questions