✏️ Explanatory Question
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?
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?
Ans. For n = 1000:
5 × 1000 × log2(1000) × 10−9 ≈ 50 × 10−6 seconds = 50 microseconds (µs)
💡 Explanation:
Since 210 = 1024, log2(1000) ≈ 10.
Therefore, the approximate number of steps is:
5 × 1000 × 10 = 50,000 steps
Since each step takes 10−9 seconds, the total execution time is:
50,000 × 10−9 seconds = 5 × 10−5 seconds = 50 × 10−6 seconds = 50 microseconds
This is much faster than the n2 and n3 algorithms for the same input size. It demonstrates why O(n log n) algorithms are highly valued for efficiently processing large inputs.
Note: Questions 12–22 repeat Questions 1–11 and use the same solutions and reasoning.