GATE CSE 2000 | Question: 2.17

Question

Consider the following functions

• $f(n) = 3n^{\sqrt{n}}$
• $g(n) = 2^{\sqrt{n}{\log_{2}n}}$
• $h(n) = n!$

Which of the following is true?

• A. $h(n)$ is $O(f(n))$
• B. $h(n)$ is $O(g(n))$
• C. $g(n)$ is not $O(f(n))$
• D. $f(n)$ is $O(g(n))$

Comments

Take log of every function If a function is less than the other then definitely It's growth function will be less but if after log if two functions differ only by constant then we can't presume them to have same growth.

---

h(n)  = n!  means approx.  n^n  which is greater of all these   so it should be O(h(n)),, no option matches
f(n) = 3n^(root n)   , taking log  gives root n * log n 
g(n) = 2^(root n * log n)  , taking log gives root n * log n 
so, f(n) = g(n),, hence worst, best, avg cases are also equal 
option D

---

@js__ that statment of yours is not true , if we take log for both and it comes out to be same then we cannot say anything 

 

Answer 1

$$\begin{array}{|l|l|l|}\hline \text{} &  \textbf{n= 256} & \textbf{n = 65536} \\ \hline \text{$f(n) = 3n^{\sqrt{n}}$} &  \text{$3 \times 256^{16}$} & \text{$3 \times 65536^{256}$}\\ & \text{$=3 \times {2^{128}}$} & \text{$ = 3 \times 2^{16 \times 256}$} \\ & & \text{$ = 3 \times 2^{4096}$}\\\hline \text{$g(n) = 2^{\sqrt{n}{\log_{2}n}}$} &  \text{$2^{16 \times 8}$}  & \text{$2^{256 \times 16}$} \\ & \text{$=2^{128}$} & \text{$ = 2^{4096}$}\\ \hline \text{$h(n) = n!$} & \text{$256!$} & \text{$65536!$}\\ & \text{$= O\left(\left(2^8\right)^{256}\right)$} & \text{$= O\left(\left(2^{16}\right)^{65536}\right)$} \\ & \text{$=O\left(2^{2048}\right)$} & \text{$=O\left(2^{1M}\right)$} \\ \hline\end{array}$$

Case of $h(n)$ is given only by an upper bound but factorial has higher growth rate than exponential. 

http://math.stackexchange.com/questions/351815/do-factorials-really-grow-faster-than-exponential-functions

$f(n)$ and $g(n)$ are having same order of growth as $f(n)$ is simply $3\times g(n)$ (we can prove this by taking $\log$ also). So, (d) is correct and all other choices are false. 

Comments

And one last line  if $\Theta (n)$  is possible  then definitely $O(n)$ and $\Omega (n)$ is also possible

---

@Arjun sir d option means f(n)<=g(n) so if we put n=1 means the result coming as 3<=1 so d option wrong na in this case?pls clarify this doubt sir

---

bro f(n)=O(g(n)) means f(n)<=c.g(n) means we can say f(n)<c.g(n)  or f(n)=c.g(n) so if any one of these holds , we can say that
Remenmber OR gate logic
 

Answer 2

1. $f(n) = 3n^{\sqrt{n}}$
2. $g(n) = 2^{\sqrt{n}{\log_{2}n}} = (2^{\log_{2}n})^\sqrt{n} = (n^{\log_{2}2})^\sqrt{n} = n^{\sqrt{n}} $
3. $h(n) = n! = o(n^n)$

So, $f(n) = g(n) < h(n) $

Therefore, (D) is the correct option!

Comments

@Krushna Kotgire

see Arjun sir explanation D is answer

---

Nice answer @Manu Thakur sir. 

---

Good Answer

Answer 3

Ans - D)

h = n! , can also be written as 

h = nⁿ (a weak upper bound on the factorial function n! <= nⁿ , as each of the n terms in the factorial product is at most n ).

This eliminates options A AND B.

And by using log property on g(n) , we observe that f(n) and g(n) vary by just a constant term of 3. 

Thus this gives us the answer D.

Comments

@Harsh181996 sir

How n! can be written as n^n

2!=2

4!=24 but 4^4=256

Answer 4

option d is correct.

Comments

Option C which you mentioned here is not correct as it was mentioned in the question.....and in case of your option...even option C must hold True.

---

this is wrong, as
here, f = O(g), g = O(f)

Answer 5

f (n) and g (n) are asymptotically equal.

and f (n)=O (g (n)) iff g (n) is asymptotically greater or equal to f (n)  

so option D is correct :-)

Answer 6

f(n) = 3n^√n  
g(n) = 2^√nlog2n

here assume n=2^128

f(n)=log(3n^√n ) here 3 is just a constant to ignore it for a while so it will be n^√n now after taking log it will be √n log n now put the value of n   so 2^64log2^128= 2^64*2^7= 2^71.

now g(n) = 2^√nlog2n  here (log2n 2 is base of log)

after taking log both side √nlog2nlog2   after putting the value of n 2^64*log2^128*log2

which is again 2^71   

here we are watching that both f(n) and g(n) are same and big O notation is valid for <= means f(n)=Og(n)

yes it can also g(n)=Of(n).

so option D is correct.