✏️ Explanatory Question

Reorder the following efficiencies from the smallest to the largest: (a) 2n (b) n! (c) n5 (d) 10,000 (e) n·log2(n)

👁 2 Views
📘 Detailed Answer
🟢 Easy
← Previous The efficiency of an algorithm is 5n·log2(n). If each step takes 1 nanosecond (10−9 seconds), how long will the algorithm take to process an input of size 1000?
💡

Answer with Explanation

Ans. 10,000 < n·log2(n) < n5 < 2n < n!

💡 Explanation:

To arrange the expressions correctly, compare how quickly each one grows as n becomes very large.

  • 10,000 is a constant, so its complexity is O(1). Its value does not change when n increases.
  • n·log2(n) is a log-linear expression. It grows faster than a linear expression but slower than any polynomial such as n5.
  • n5 is a polynomial expression. It grows faster than n·log2(n) but slower than an exponential expression.
  • 2n is exponential and eventually grows faster than every fixed-degree polynomial.
  • n! is factorial and grows faster than all the other expressions in the list.

Therefore, the correct order is: constant → log-linear → polynomial → exponential → factorial .

Memory tip: O(1) < O(n log n) < O(nk) < O(2n) < O(n!)

← Previous The efficiency of an algorithm is 5n·log2(n). If each step takes 1 nanosecond (10−9 seconds), how long will the algorithm take to process an input of size 1000?