MIT assigment

Question

Arrange the following functions in their increasing order of complexities.

$f(n) = n ^{0.999999} * \log n$          ($\log n$ is not in power)

$g(n) = 10000 n$

$h(n) = n^{2}$

$k(n) = (1.000001)^{n}$

$p(n) =\large \frac{2 ^{√n}}{ n^{2}}$

$q(n) = \Large \frac{n^{1.000001}}{\log n}$

Comments

my answer is-

f<q<g<h<p<k

someone plz cross check?

---

I got f<q<g<h<k<p

what is n2?? it will be $n^{2}$ right??

---

plz use latex

---

How did u solve? Did u calculate the Limit for everything as n approaches Infinity?

---

in p(n) is it 2 ^√n / n2 or 2 ^√n / n^2??

if u took this 2 ^√n / n^2

then k(n)<p(n)<q(n)<g(n)<f(n)<h(n)

---

YES LIMIT

---

YES ITS N^2. PLZ SOLVE IT SRETHA

---

$n\log 1.000001$

$\log 1.000001< < < 1\simeq 0$

So,$n\rightarrow 0.0000....n$

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

$\log \frac{2^{\sqrt{n}}}{n^{2}}=\sqrt{n}-2\log n$

---

taking log for both the functions

---

how to use latex?

---

what is your final answer?

---

go to fx button and press it, and use mathematical symbol from there

anything inside two $ symbol is latex

I have edited

---

thanks :)

---

anything wrong, then plz tell me

Answer 1

$f\left ( n \right )=\Theta \left ( n^{0.999999}*\log n \right )\simeq \Theta \left ( n \log n\right )$

$g\left ( n \right )=\Theta \left ( 100000 n \right )\simeq \Theta \left ( n\right )$

$h\left ( n \right )= \Theta \left ( n^{2}\right )$

$k\left ( n \right )= \Theta \left ( \left ( 1.00001 \right )^{n}\right )$

$p\left ( n \right )= \frac{2^{\sqrt{n}}}{n^{2}}\simeq\Theta \left ( 2^{\sqrt{n}} \right )$

$q\left ( n \right )= \frac{n^{1.000001}}{\log n}\simeq\Theta \left ( n \right )$

So,order of growth rate $ g< q< f<h<k<p$

for total diagram https://www.desmos.com/calculator/fiepklrawo

 

Comments

@ankitgupta

u can chk the link I provided.

Still It has a theoritical thinking $\left ( 1.000001 \right )^{n}\simeq \left ( 1 \right )^{n}\simeq 1=\Theta \left ( 1 \right )$

Can u tell me anything wrong?

@Somoshree

Similarly

it have to be much much larger than u thinking

because it grows $n^{1.000001}$, which is very small but growing polynomially

but $10000n$ is growing linearly

---

Hello srestha ,Good Morning! . 

Actually , $(1.000001)^{n}$ is not a constant function. It is an exponential function. It is of the form $c^{n}$ , where , $c>1$.

You can check this question also :- https://gateoverflow.in/3270/gate2008-it-10

When you zoom out the your graph then you will know the exponential nature of this function because , for asymptotic behavior of a function , we have to check large values of '$n$' . You can understand it as $(1.000001)^{n} = (1000001*10^{-6})^{n}= \frac{(1000001)^{n}}{10^{6n}} = (\frac{10^{6}+1}{10^{6}})^{n} .$. It is like the graph of $(\frac{3}{2})^{n}$ because  here Numerator and denominator have difference of only 1 but it shows high growth rate..you can check it by plotting the graph and do zoom-in and zoom-out.

I am attaching the screenshot of this exponential behavior. PFA

 

---

Good Morning

yes @ankit

thank u so much :)

updated