The Gateway to Computer Science Excellence
+35 votes
3.8k views

Arrange the following functions in increasing asymptotic order:

  1. $n^{1/3}$
  2. $e^n$
  3. $n^{7/4}$                                                                              
  4. $n \log^9n$
  5. $1.0000001^n$
  1. a, d, c, e, b
  2. d, a, c, e, b
  3. a, c, d, e, b
  4. a, c, d, b, e
in Algorithms by Boss (16.3k points)
edited by | 3.8k views
+1

How $\text{C > D}?$

$\Large \lim_{n \rightarrow \infty} \frac{n^{\frac{7}{4}}}{nlog^9 n}$

$\Large \lim_{n \rightarrow \infty} \frac{n^{\frac{3}{4}}}{log^9 n}$

This limit evaluates to $\infty$ which means $\text{C > D}?$

2 Answers

+37 votes
Best answer
$A < C$ and $A < D$ are straight forward.

$E < B$ and $C, D < E$ as $E$ and $B$ are exponential functions and $B$ having a larger base.

Now, we just need to see if $C$ or $D$ is larger.

In $C$ we have a term $n^{3/4}$ and correspondingly in D we have $\log^9n$ (after taking $n$ out).

$n^{3/4}$ is asymptotically larger than $\log^9n$ as when $n = 10^{100}, \log^9 n$ gives $100^9$, while $n^{3/4}$ gives $10^{75} > 100^{37}$ a much higher value and this is true for all higher values of $n$. So, D < C.

Thus, $A$ is correct.
by Veteran (423k points)
edited by
+1

"In C we have a term n3/4 "  But C is given  n7/4 

how did n3/4 came ?

0
how did n^3/4 come?? #arjun Sir
+2
That is after taking $n$ out as it is common for C and D. I have edited it..
0
in option E ,power 'n' is over only 1 otr is it like (1.0000001)^n??
0
It is over the whole number (second case).
0

I have a confusion here arjun sir, in the CLRS book its clearly mentioned that login = (logn)i and successive logarithm function is the log* function which has the following notation - log(i)n.

So, how are you applying log* funtion here ? Shouldn't it be - (logn)instead ?

0
For larger value of n what is the value of 1.0000001^n? Is it 1.0000000.....1?
+4

arjun sir I think the question does not state the recursive log instead log n * logn ...9 times. 

http://math.stackexchange.com/questions/150546/what-does-log2x-mean

+1
yes, that was a mistake.. Corrected now..
0
we were comparing 100^9 and 10^75 . How 10^37 came in picture sir.
+1
$10^{75} = 10.{10^{2}}^{37}= 10.100^{37}$
0
@arjun sir for any large value of n value of option e is less than option c.please correct me where am i going wrong
+1
not getting how E be in 4 position

 i caluculated its value to large n

which still at 1.000..?
+2
if you have doubt you can try plotting the graph and see. Large value means some large value - can be even one with 100 digits - for the same reason we cannot always find this by substituting values.
+1

@arjun sir

how is E greater than C and D ?

we can assume 1.000000001 as 1

1anything = 1

where am i going wrong

+1
^

 |

 |__________ Your assumption itself is wrong!

Hint:  Find 1.0000001^(1024*1024*1024)  

         //and keep on increasing the value of n until you are satisfied.
0

@hiigs

C, D < E

i dont understand how

+10

^You might be aware of the fact that the exponential functions grow much faster than polynomial functions.


Let us assume for now that for all values of n, e < d and e < c.


Now lets illustrate by counterexample that our assumption based on our intuition is wrong!

Consider some large value of n.

Let n = 2^32

c) (2^32)^1.75              = 7.2057594e+16

d) (2^32)(log 2^32)^9 = 3.0675921e+18                  //base 10   

e) 1.0000001^(2^32)    = 3.373265e+186

Hence, our intuition based assumption that for all values of n, e < d and e < c is false.


Let's visualise these functions:

//Observe colors infront of the functions to find the corresponding curve in the graph

// Eg: Red <=> n^1.75

Above graph justifies our intuition that  1.0000001^n is approx 1^n i.e. is 1.

Lets zoom out a bit.

Still the curve of 1.0000001^n is hovering around 1.

Let's zoom out more.

Still nothing.

Voilla!

Observe how 1.0000001^n has stopped hovering around 1 and grown so quickly as n has become large.

As we keep on increasing n, at some point e) will overtake c) and d) as we have seen in our

calculation performed above.


PS: 1) Don't confuse between 1.0000001^32 and 1.0000001^(2^32)  .

                                                      ^                           ^

                                                       |                             |

                                                   = 1                          = 3.373265e+186

     2) From above calculation as well as graphs, it appears that c < d, therefore option(c)

        looks like more apt. answer.  

0
got it :)

thanks a ton @higgs
0
@Arjun sir

Why are you comparing $10^{75}$>$100^{37}$. Are you trying to show that when 10^75 is written in terms of 100^37,then still it is larger?
+1

@ rahul

we reach a stage where we have to compare between 1009 and 1075

so 1075 is converted in terms of 100 as 10037 to make it easy for comparison 

we can now definetelity and clearly see that 10037 > 1009

0
explain about d
0
@arjun sir

how log^9(n)=100^9, when n=10^100?
0
arjun sir is there any method to solve this question easily. i tried to solve this question by simply putting n=1 becoz of calculator but at some point i do some mistake can you share any approach .
0
Can anyone help solving this more easily. It seems too much complicated
0
default base is 2 so why to assume n=10^100  instead of 2^100
0

@Arjun sir

Default base is 2 and suppose if we take $2^{128}$ to check for options (C) and (D). After taking 'n' as common as already mentioned in above answer.

For option (C) : $2^{128*3/4} = 2^{96}$

For option (D) : ${[log 2^{128}}]^{9} = 128^9 = [2^7]^9 = 2^{63}$    

In this way C>D

Please mention where i m going wrong ?

0

@ yeah In the above solution also C>D & we've to arrange in the increasing order.

0
Thanks man.
+3 votes

Here we've to eliminate options one by one.

check 1st letter of every option,there we've a confusion about A & D, so now let's compare between A & D

$n^{1/3}$  &  $nlog^{9}n$   $\Rightarrow$   $\frac{logn}{3}$  & logn + 9loglogn

So clearly D is bigger than A, i.e option B is out.

Now let's take next two letter in the remaining  options d,c. here we've a confusion b/w d & c,

$nlog^{9}n$  &  $n^{7/4}$   $\Rightarrow$   $log^{9}n$  &  $n^{3/4}$  

take n = $10^{100}$  then  $n^{3/4}$  = $10^{75}$    &    $log^{9}n$ = $10^{18}$ i.e  D<C

Now we can eliminate option C & D also and remaining option A is the answer.

If we Compare B & E ,  $e^{n}$  & $1.0000001^{n}$  (take log base e on both side) 

It becomes n & n.$\ln(1.0000001)$  which clearly shows B>E

Finally a, d, c, e, b  which is option A

by Active (2.9k points)
0
how   log^9n=10^18
+1
take logn base 10

$log^{9}n = (\log_{10}n)^{9}$

now put $n=10^{100}$  means  $(\log_{10}10^{100})^{9} = 100^{9}=(10^{2})^{9}=10^{18}$
0
thanks

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
50,650 questions
56,236 answers
194,264 comments
95,870 users