The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+27 votes
4k views

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?

  1. $h(n)$ is $O(f(n))$
  2. $h(n)$ is $O(g(n))$
  3. $g(n)$ is not $O(f(n))$
  4. $f(n)$ is $O(g(n))$
asked in Algorithms by Veteran (59.5k points)
edited by | 4k views
0
can any one answer this. These types of questions always confuse me.
0
I have  a doubt related to  this question since both f(n) and g(n) having same growth and answer given is d means by default big o notation is always theta notation ?
+1
Not necessarily.If big oh condition is satisfied then it is also possible that big omega will not be satisfied.As we know theta is satisfied if both big oh and big omega are satisfied simultaneously.

Hence if big oh is satisfied then theta notation may or may not be theta.

Here since f(n) = Theta(g(n)) so both big oh and big omega is satisfied hence option D is true.
+2

Both f(n) and g(n) are asymptotically equal. Caculcating log2 of both the functions you will get

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

g(n) = √n log n

Now as this function is clearly equivalent and we can find constants such that

1) cg(n) > f(n) any C>1

2) cg(n) < f(n) any c>0 and C<1

Hence g(n) can be both upper and lower bounds.

@ anshul

For most g(n) = O(f(n)) there does not exsist any constant c such that Cf(n) < g(n). hence it is not necessary that all big 0 functions satisfy theta condtion. But the converse is always true. i.e All theta functions satisfy big O condition.

0
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.

4 Answers

+36 votes
Best answer
  $n = 256$ $n=65536$

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

$3 \times 256^{16}$

$=3 \times {2^{128}}$

$3 \times 65536^{256}$

$ = 3 \times 2^{16 \times 256}$

$ = 3 \times 2^{4096}$

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

$2^{16 \times 8}$

$=2^{128}$

$2^{256 \times 16}$

$ = 2^{4096}$

$h(n) = n!$

$256!$

$= O\left(\left(2^8\right)^{256}\right)$

$=O\left(2^{2048}\right)$

$65536!$

$= O\left(\left(2^{16}\right)^{65536}\right)$

$=O\left(2^{1M}\right)$

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. 

answered by Veteran (353k points)
edited by
0
Thanks !!!
0
for solving these type of questions is this the quickest way? ... because in a competition every second counts !!!
+12
I guess this procedure can be done really quick on paper. If you are not comfortable with power of 2's, you can use power of 10's and take log to the base 10. More than time, you should follow techniques which never gives wrong answer. That is more important for GATE.
0
I am satisfied with the logic that asymptotically f(n) and g(n) are equal hence f(n) is O(g(n)) would not be a wrong answer.

But if we discuss asymptotically (not on behalf of some numerical example values) then factorial means that every time it is multiplying by a value one less than previous one i-e n*n-1 ....*1

But n ^√n means we are every time multiplying n by n i-e n*n.......*n (√n times).

So how could h(n) be greater than f(n) or g(n) [ASYMPTOTICALLY].
+3
@G.K.T. Good doubt.Take some large $n$. For $n^{\sqrt n}$ we multiply $n$ $\sqrt n$ times, i.e., $\sqrt n$, $n$ times. For $n!$, we have $n- \sqrt n$ values which are larger than $\sqrt n$ and one value equal to $\sqrt n$ and $\sqrt n - 1$ values smaller than $\sqrt n$ in the multiplication part. If we consider the first 2 parts we get ${\sqrt n} ^ {n - \sqrt n + 1}$. Now, we have $\sqrt n$ terms smaller than $\sqrt n$ and all $n - \sqrt n$ terms were larger. Since $\sqrt n <<< n - \sqrt n$, this means asymptotically, $n! > n^{\sqrt n}.$
+1
Thanks Arjun sir ,very nice explanation you given which cleared my doubt.Now i can see how n! Is much larger than n^√n .
0
is that mean g(n) grows faster than f(n)?
0
isnt it that multiply root(n) 2*n times??
0
@Pravin f(n) is always larger than g(n), but grows at same rate.

@Pinky which one?
+1
do g(n)=O(f(n)) correct for this question ??
+1
yes correct.
+1
let f(n),g(n) be inreasing function.it is given
f(n)=O(g(n)) and g(n)=O(f(n))
then ,wht does it mean?it is same case in this question !!!
+4
+1
Also,

f(n)=theta(g(n))
iff f(n)=0(g(n))
and
f(n)=omega(g(n))
+4
No. Both f(n) and g(n) are O ( big oh) of each other. Hence answer is absolutely correct. Wats the confusion?
0
plz help...

i am getting g(n) = O(f(n))

what does this mean f(n) is O(g(n))  or g(n) is O(f(n))

i think it should be g(n) is O(f(n)) plz correct me if i am wrong.
+1

Both f(n) and g(n) are asymptotically equal. Caculcating log2 of both the functions you will get

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

g(n) = √n log n

Now as this function is clearly equivalent and we can find constants such that

1) cg(n) > f(n) any C>1

2) cg(n) < f(n) any c>0 and C<1

Hence g(n) can be both upper and lower bounds.

For most g(n) = O(f(n)) there does not exsist any constant c such that Cf(n) < g(n). hence it is not necessary that all big 0 functions satisfy theta condtion. But the converse is always true. i.e All theta functions satisfy big O condition.

0
@ arjun sir, can we always take log to compare the asymptotic growth? I have got a confusion all of a sudden. If we have n^2 and n^3, and we take log we will get 2logn and 3 logn which are same asymptotically. So how log methods ensures correct result??
0
f(n) = log 3 + √n log n

g(n) = √n log n. Here both the functions are equivalent as one function differs from the other by just a constant term and will be the value of log 3(as it added) i.e the difference does not grow at all. But 2logn and  3logn the value by which they differ depends upon n, as two and three are multiplied to variable term. And as log is used it means that they differ exponentially.
0
sir can uh pleas explain how the factorial has higher growth rate than exponential.1?? i am not getting
+16 votes

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!

answered by Boss (39.8k points)
0
Best Answer ...
0
thanks Puja!
+7 votes

Ans - D)

h = n! , can also be written as 

h = nn (a weak upper bound on the factorial function n! <= nn , 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.

answered by Active (4k points)
+4 votes
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 :-)
answered by Junior (853 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,117 questions
44,701 answers
127,278 comments
43,765 users