Asymptotic-Complexity
Question 1 |
Consider the following functions from positives integers to real numbers
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
![]() | |
![]() | |
![]() | |
![]() |
Question 1 Explanation:
In this problem, they are expecting to find us “increasing order of asymptotic complexity”.
Step-1: Take n=2048 or 211 (Always take n is very big number)
Step-2: Divide functions into 2 ways
1. Polynomial functions
2. Exponential functions
Step-3: The above functions are belongs to polynomial. So, simply substitute the value of n,
First compare with constant values.
→ 100 / 2048 = 0.048828125
→ 10 > 100/ 2048
→ log2 2048 =11
→ √n = 45.25483399593904156165403917471
→ n = 2048
So, Option B is correct
Step-1: Take n=2048 or 211 (Always take n is very big number)
Step-2: Divide functions into 2 ways
1. Polynomial functions
2. Exponential functions
Step-3: The above functions are belongs to polynomial. So, simply substitute the value of n,
First compare with constant values.
→ 100 / 2048 = 0.048828125
→ 10 > 100/ 2048
→ log2 2048 =11
→ √n = 45.25483399593904156165403917471
→ n = 2048
So, Option B is correct
Question 2 |
f3, f2, f4, f1 | |
f3, f2, f1, f4 | |
f2, f3, f1, f4 | |
f2, f3, f4, f1 |
Question 2 Explanation:
If they are expecting to find an asymptotic complexity functions means
→ Divide functions into 2 categories
1. Polynomial functions
2. Exponential functions
Above 4 functions we have only one exponential function is f1 (n) = 2n . So, It’s value is higher than to rest of the functions.
Substitute log on both sides then we get an ascending order is f3, f2, f4.
→ Divide functions into 2 categories
1. Polynomial functions
2. Exponential functions
Above 4 functions we have only one exponential function is f1 (n) = 2n . So, It’s value is higher than to rest of the functions.
Substitute log on both sides then we get an ascending order is f3, f2, f4.
There are 2 questions to complete.