Which of the given Options provides the increasing order of asymptotic complexity of functions f1, f2, f3, and f4? f1(n) = 2n f2(n) = n3/2 f3(n) = n log2 n f4(n) = nlog2n
Which of the given Options provides the increasing order of asymptotic complexity of functions f1, f2, f3, and f4? f1(n) = 2n f2(n) = n3/2 f3(n) = n log2 n f4(n) = nlog2n Correct Answer f<sub>3</sub>, f<sub>2</sub>, f<sub>4</sub>, f<sub>1</sub>
The correct answer is option 1
Explanation:
Taking log base 2 on all the functions
| Function | Taking log | Taking a large number n = 220 |
| f1(n) = 2n | f1(n) = n× log22 = n | f1 = 220 |
| f2(n) = n3/2 | f2(n) = 3/2 log2n | f2 = (3/2) × log2220= (3/2)× 20 =30 |
| f3(n) = n × log2 n | f3(n) = log2 n +log2 log2 n | f3 = log2220 +log2 log2 220 = 25 |
| f4(n) = nlog2n | f4(n) = log2 n × log2 n
|
f4 = log22 20× log2 220= 20 × 20=400 |
Increasing order of asymptotic complexity of functions f1, f2, f3 and f4 is f3 < f2 <f4 < f1
মোঃ আরিফুল ইসলাম
Feb 20, 2025