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

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.

Answer 2

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.

Answer 3

f(n)=theta(g(n)).

h(n)=n!   g(n)=n^root n.

apply log both sides.

log(n!)  and     rootn *log(n);

but since log(n!)=theta (nlogn)    and  nlogn >rootn *logn. so we can say n!>n^rootn.

is my approach correct?

Answer 4

f(n) = n2logn; g(n) = n(logn)10
Cancel nlogn from f(n), g(n)
f(n) = n; g(n) = (logn)9
n is too large than (logn)9
So f(n)! = O(g(n)) and g(n) = O(f(n))

 

Hence option D is right