The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+25 votes
3.9k views

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 (6.9k points)
edited by | 3.9k views
+1
0

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

9 Answers

+33 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 (418k points)
edited by
0
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?
0
I have already given that at end rt? You have to focus on growth rate and not the value at some large point.
0
Okay Thank you sir!
0

@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?? 

+26 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 (62.3k points)
edited by
+13 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 (1.9k points)
+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 (17.9k points)
+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

by Boss (16.6k points)
+5 votes

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

by Active (2.9k points)
+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 (17.9k points)
+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 (1.1k points)
0 votes
(B) 100n100n, 1010, log2nlog2⁡n, n−−√n, n
by Active (3.9k points)
Answer:

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
49,896 questions
55,153 answers
190,577 comments
85,317 users