1 is also added:

The Gateway to Computer Science Excellence

+28 votes

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:

- $\log_{2}n$, $\frac{100}{n}$, $10$, $\sqrt{n}$, $n$
- $\frac{100}{n}$, $10$, $\log_{2}n$, $\sqrt{n}$, $n$
- $10$, $\frac{100}{n}$, $\sqrt{n}$, $\log_{2}n$, $n$
- $\frac{100}{n}$, $\log_{2}n$, $10$, $\sqrt{n}$, $n$

+39 votes

Best answer

$10$ is constant. $\therefore$ Growth rate is $0$.

$\sqrt{n}$ grows slower than linear but faster than $\log$. (Consider $\frac {\sqrt {n^2}}{\sqrt n} =\sqrt n$, whereas $\frac {\log \left(n^2\right)}{\log n} = 2$)

$n$ : Growth rate is linear.

$\log_{2}n$ : Growth rate is logarithmic. For asymptotic growth, the base does not matter.

$\frac{100}{n}$ : Growth rate decreases with $n$.

So, correct answer is **(B)**.

NOTE: Please never substitute large values of $n$ in such questions. If ever you do, at least do for $2$ such values and take ratio to get the growth rate or plot a graph. Remember ${1.01}^{n} \neq O\left(n^{100}\right)$.

+28 votes

- $10$, Constant
- $\sqrt{n}$, Square root
- $n$, Polynomial
- $\log_{2}n$, Logarithmic
- $\frac{100}{n}$. Constant division by polynomial
**(clearly less than constant for every value of n >100)**

Now we know Constant division by polynomial < Constant < Logarithmic <Square root < Polynomial

So, correct order is $\frac{100}{n}$, $10$, $\log_{2}n$, $\sqrt{n}$, $n$

PS: In the above graph, for asymptotic notations any graph can be multiplied by a constant and so the $\textbf{SLOPE}$ is the important factor. If any plot is having higher slope, it'll eventually overtake the lower slope one at some value of $x$ and hence asymptotically larger than the other.

+13 votes

+10 votes

if we take a very large value of n suppose =2^{1024}

then we can follow the sequence with result

100/2^{1024 }<10 < log1024=1024 <sqrt(2^{1024) } < 2^{1024}

so following we see B is the correct answer

+7 votes

100/n grows inversely with n so for very large values of n, it will become close to zero.

10 IS CONSTANT.

100/n<10

among rest of choices it is very clear that

log n < sqrt(n)<n

thus 100/n<10< log n < sqrt(n)<n

**CHOICE B**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,650 questions

56,242 answers

194,294 comments

95,945 users