asymtotic notations

Question

Q). Consider the following functions

$f_1 = n^{\frac{4}{3}}$

$f_2=2^{2^n}$

$f_3= 2^{n^2}$

$f_4= n!$

$f_5=2^n$

Which of the following is true?

A). $f_1$ is $\Omega(f_2)$

B). $f_2$ is $O(f_3)$

C). $f_1<f_5<f_4<f_2<f_3$

D). $f_4$ is $O(f_3)$

Answer 1

Function                      Take log in every function

f₁=n^4/3                                                         4/3 log n    

f₂ = 2^{2^n}                                                                   2ⁿ

f₃=2^{n^2}                                                            n² 

f₄ = n!                                                           n log n

f₅=2ⁿ                                                                   n

Logarithmic growth rate of  f1  is less than all other functions growth rate 

Linear growth rate of f₅  is more than logarithmic growth rate of f₁

 Linear growth rate of f₄  is more than logarithmic growth rate of f₅

Non linear growth rate of  f₃ is more than linear growth rate of f₄

Exponential growth rate of f₂ is more than non linear growth rate of f₃

So, f₁ <  f₅  < f₄ < f₃ < f₂

So, ans will be (D)

Comments

if we write f2= 4^n and than if we take log it will be equal to 2n in this way f2 would be less than f3 and f4..so can we write f2 as 4^n??

---

See power function  is right associative So U have to evaluate it from right to left like this (2^{(2^n)})

i.e. 2ⁿ first then (2^{(2^n)})

---

ok.. thank you :) :)

Answer 2

I think option D is true. first of all . 1 is a linear function, secondly in exponential we have 2 functions that are f4,f5. in which n^n has a much bigger growth than 2^n. and then we have 2 super exponential functions that are f2 and f3.  as 2^n has a much greter growth than n^2. f3=O(f2). now just compare n^n and 2^ n^2.

taking log both side. nlogn =n^2 log 2

nlogn=n2. so option d .

Comments

what u are asking . ??? why A is not true?/

---

yes why not A

---

a is saying the complexity of f1 is not less than of f2. f1 is a polynomial time while f2 is exponential time. so A litreally means polynomial time complexity is not less than exponential time.