✏️ 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, we can approximate:
log2(1000) ≈ 10
Therefore, the approximate number of steps is:
5 × 1000 × 10 = 50,000 steps
Since each step takes 1 nanosecond = 10−9 seconds, the total execution time is:
50,000 × 10−9 seconds = 5 × 10−5 seconds = 50 × 10−6 seconds = 50 microseconds
Therefore, the algorithm takes approximately 50 microseconds (µs).
Memory tip: Because log2(1000) ≈ 10, replace the logarithmic value with 10 for a quick approximate calculation.