The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+25 votes
1.6k 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
asked in Algorithms by Veteran (21.9k points)
edited by | 1.6k views

1 Answer

+26 votes
Best answer
A < C and A < D

E < B

and

C, D < E as E is exponential function.

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.
answered by Veteran (332k points)
edited by
@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
not getting how E be in 4 position

 i caluculated its value to large n

which still at 1.000..?
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.

@arjun sir

how is E greater than C and D ?

we can assume 1.000000001 as 1

1anything = 1

where am i going wrong

^

 |

 |__________ Your assumption itself is wrong!

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

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

@hiigs

C, D < E

i dont understand how

^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.  

got it :)

thanks a ton @higgs
@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?

@ 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



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

32,732 questions
39,309 answers
110,280 comments
36,733 users