Consider the following functions from positive integers to real numbers: \(10,…
2017
Consider the following functions from positive integers to real numbers:
\(10, \sqrt n, \ n ,\ log_2 \ n, \frac {100} {n}\)
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
- A.
\(log_2 \ n ,\frac {100} n, 10 ,\sqrt n, n\) - B.
\(\frac {100} n ,10, log_2 \ n, \sqrt n, n\) - C.
\(10, \frac {100} n ,\sqrt n, log_2 \ n , n\) - D.
\(\frac {100} n, log_2 \ n, 10 , \sqrt n , n\)
Attempted by 289 students.
Show answer & explanation
Correct answer: B
Key insight: compare the functions by their behavior as n → ∞.
100/n = Θ(1/n) tends to 0, so it grows the slowest (smallest asymptotically).
10 is a constant (Θ(1)), larger than 100/n for large n but smaller than any unbounded function like log2 n.
log2 n grows without bound but very slowly; it is o(n^a) for any a>0, so it comes before sqrt n.
sqrt n = n^{1/2} grows faster than log2 n but slower than n.
n grows fastest among the listed functions.
Final order (increasing asymptotic complexity): 100/n, 10, log2 n, sqrt n, n
A video solution is available for this question — log in and enroll to watch it.