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

just dont try to ans it forcefully by assuming that f is order of G, No f is always bigger of G so, ans is None.

---

given that

f(n) = log 3 + √n log n

g(n) = √n log n

we can prove that f(n)=O(g(n)) i.e. if we are able to select a constant c(c>=0) such that f(n)<=cg(n)

now if we take c=(log3+1) then our work is done

---

f(n) = $3n ^{\surd n}$

g(n) = $n ^{\surd n}$

h(n) = n!

Clearly f(n) = O(g(n)) and g(n) = O(f(n))

Now, let y = n!, taking log both sides logy = logn!, by Stirling's approximation logy $\approx$ nlogn

let z = $n ^{\surd n}$, taking log both sides logz = $\surd nlogn$
Hence, f(n) = o(h(n)), g(n) = o(h(n)), as h(n) strictly upperbounds f(n) and g(n).

https://mathworld.wolfram.com/Little-ONotation.html

https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation

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

Simply, factorial function has higher growth rate than exponential. So, (A) and (B) are wrong.

Asymptotically, $f(n) = g(n) = \sqrt{n}log_2n$ (This can be proved by taking log both side of f(n) and g(n).

Hence, we can say either $f(n)\ is\ O(g(n))$ or $g(n)\ is\ O(f(n))$.

So, option (D) is right choice.

---

@Amal I would like to add one thing. To solve this q by taking log on both sides is an incorrect method. This is because if log of two functions are equal then the two functions may or may not be equal.

Proof:-

Let $f(n) = n^2$ and $g(n) = n^3$;

It is very clear that $f(n) = O(g(n))$ 

But, taking log on both sides, $log(f(n)) = log(g(n)) = log(n)$

due to which we may conclude $f(n) = \Theta(g(n))$ and it is wrong.

Thus the correct method for f(n) and g(n) in this q:-

$f(n) = 3n^{\sqrt{n}}$ and $g(n) = 2^{\sqrt{n}{\log_{2}n}}$

$g(n) = 2^{log_{2}{n}^{\sqrt{n}}} = n^{\sqrt{n}} = f(n)$

Thus, $f(n) = \Theta(g(n))$

---

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

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

Here h(n)>f(n)>g(n)

Then all options are wrong ans must be none of the above.

---

@Krushna Kotgire, Using Big-O notation, f(n)=g(n), so they both are asymptotically same.

---

@Krushna Kotgire

see Arjun sir explanation D is 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

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 :-)