GATE CSE 2017 Set 1 | Question: 04

Question

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$

Comments

1 is also added:

https://gateoverflow.in/tag/gate2017-1?start=30

---

Hi, if we take n=2¹⁰²⁴ , then logn gives me 1024, which is greater than 10. So why D won't be the answer?

---

The same type of concept asked in

• GATE IT 2008 | Question: 10
• GATE CSE 2011 | Question: 37,
• GATE CSE 2021 Set 1 | Question: 3

---

If 1024 is greater than 10 so logn is greater than 10 which is option B is  correct.

Answer 1

(B) 100n100n, 1010, log2nlog2⁡n, n−−√n, n

Answer 2

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

Answer 3

100/n < 10 < log2 n < √n < n 

Answer 4

according to the increasing order of complexitites it is clear that
Constant < < logn < < n^(1/2) < < n
So the conflict is in between 100/n and 10 here for values  n <= 9, 10 < 100/n
but the question is about positive integers to real numbers so this section from 1 to 9 is  <<<<« than positive integers so option B will be correct