GATE IT 2008 | Question: 10

Question

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$

• A. a, d, c, e, b
• B. d, a, c, e, b
• C. a, c, d, e, b
• D. a, c, d, b, e

Comments

https://www.youtube.com/live/-l0Gy_i47NE?si=8tu4MxOTkhlbIson&t=11377

see this go class video and everything will be cleared.

 

here only trick is n pow 7/4 and logn .(and also 1.000..0 ^n )!

---

@Karthiga_Sampath i think you can use binomial exapnsion for this as ,

1.0000001^n =(1+0.0000001)^n 

---

Done ✅

Answer 1

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

Comments

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

---

Thanks man.

---

Similar type of que asked in:

• GATE CSE 2011 | Question: 37
• GATE CSE 2017 Set 1 | Question: 04
• GATE CSE 2021 Set 1 | Question: 3

Answer 2

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

Comments

how   log^9n=10^18

---

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}$

---

thanks

Answer 3

All other options are pretty straight forward, Only problem i faced in comparing C and D option
n^(7/4) and n(log n)^9

take log both side

1. (7/4)logn and log(n * (log n)^9)
2. (7/4)logn and log(n) + log(log n)^9)
3. (3/4)logn and 9log(log n)

now let take log n = k

     4. (3/4)k and 9logk

     5. c1 * k and c2 * log k

as we know that k > log k

hence proved c > k

Comments

nice explanation

Answer 4

A < D < C < E < B
n1/3 < n log9 < n7/4 < 1.0000001n < en

Answer 5

Usefull to remember:(a,b are positive)

if a>b>0 then n^a > n^b

AND

if a>b>0 then a^n > b^n

 

let's take:

A = n^(1/3)

B = e^n

C = n^(7/4)

D = n (log n)^9

E = (1.0000001)^n

 

-------------------------------------------------

Step 1: Take logs (log is increasing, so order is preserved)

 

log A = (1/3) * log n

log B = n

log C = (7/4) * log n

log D = log n + 9 log log n

log E = n * log(1.0000001) = c n, where c ≈ 0.0000001 > 0

 

-------------------------------------------------

Step 2: Compare the logs for large n 

 

(1/3) log n << log n + 9 log log n << (7/4) log n << c n << n

 

- Among log-based terms: 1/3 * log n < log n + 9 log log n < 7/4 * log n.

- Linear terms (c n, n) dominate any log terms.

 

-------------------------------------------------

Step 3:

 

n^(1/3) < n (log n)^9 < n^(7/4) < (1.0000001)^n < e^n

Result (smallest to largest growth):

 

A < D < C < E < B