✏️ Explanatory Question

Determine the Big-O notation for the following expressions:

(a) 5n5/2 + 12n2/5
(b) 6·log2(n) + 9n
(c) 3n4 + n·log2(n)
(d) 5n2 + 13n3/2

👁 2 Views
📘 Detailed Answer
🟢 Easy
← Previous Reorder the following efficiencies from the smallest to the largest: (a) n·log2(n) (b) n + n2 + n3 (c) 24 (d) n0.5
💡

Answer with Explanation

Ans.
(a) O(n5/2)
(b) O(n)
(c) O(n4)
(d) O(n2)

💡 Explanation:

To determine the Big-O notation of an expression, keep only the fastest-growing term and remove its constant coefficient. Lower-order terms become insignificant as n grows.

  • (a) Between n5/2 and n2/5, the exponent 5/2 is larger. Therefore, the result is O(n5/2).
  • (b) The linear term n grows faster than log2(n). Therefore, the result is O(n).
  • (c) The polynomial term n4 grows faster than n·log2(n). Therefore, the result is O(n4).
  • (d) Since 2 > 3/2, n2 grows faster than n3/2. Therefore, the result is O(n2).

Memory tip: For a sum of terms, compare their growth rates, select the fastest-growing term, and then drop its coefficient.

← Previous Reorder the following efficiencies from the smallest to the largest: (a) n·log2(n) (b) n + n2 + n3 (c) 24 (d) n0.5