The Gateway to Computer Science Excellence
+35 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:

  1. $\log_{2}n$, $\frac{100}{n}$, $10$, $\sqrt{n}$, $n$
  2. $\frac{100}{n}$, $10$, $\log_{2}n$, $\sqrt{n}$, $n$
  3. $10$, $\frac{100}{n}$, $\sqrt{n}$, $\log_{2}n$, $n$
  4. $\frac{100}{n}$, $\log_{2}n$, $10$, $\sqrt{n}$, $n$
in Algorithms by Loyal
edited by | 4.9k views

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

10 Answers

+46 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)$.

by Veteran
edited by
Sir can you please explain this concept of not using large values in these type questions? That method is easy so where does it goes wrong?
I have already given that at end rt? You have to focus on growth rate and not the value at some large point.
Okay Thank you sir!

@Arjun Sir

Remember ${1.01}^{n} \neq O\left(n^{100}\right)$.

why this line given?? Here one is exponential power and other one polynomial power. How these two could be related?? 

If in the question, increasing order of "growth rate" was asked then 10 would come before 100/n right?
+31 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.

by Veteran
edited by
The graph explains the order in a nutshell.
+12 votes

Here I m using the term win but that I dont think is right..I have been using this for my own understanding purposes..

by Active
+10 votes

if we take a very large value of n suppose =21024

then we can follow the sequence with result

100/21024 <10 < log1024=1024 <sqrt(21024)  < 21024 

so following we see B is the correct answer

by Boss
+7 votes

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



among rest of choices it is very clear that

log n < sqrt(n)<n

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


by Boss
+5 votes

O(100/N), O(10), O(logN), O(N1/2), O(N)

by Active
+5 votes

let take  a very large N value of 21024

Now putting this in the respective  terms we get

B is the correct answer here

NOTE: More editing coming up 

by Boss
+1 vote
Easily comparison by taking a log of all the value and put n equals to the large value.

We get option B is correct order
by Active

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,217 questions
59,907 answers
118,146 users