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

Here, we will rewrite these functions in such a manner that is suitable for asymptotic comparison:

Refer below image

Answer 2

take log for all 3 functions, and consider only higher power functions. 

f(n)  = sqrt(n)logn

g(n) = sqrt(n)logn

h(n) = nlogn

f(n) and g(n) growth order is same and is less then h(n).

do only option D satisfies.