The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+31 votes
4.6k 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.6k points)
edited by | 4.6k views
+1
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.
+4

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.

5 Answers

+42 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 (362k points)
edited by
+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
0
@Arjun sir

How is n multiplied √n times equivalent to √n multiplied n times? Take n=9 for counter example.
+21 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 (41k points)
0
Best Answer ...
0
thanks Puja!
+6 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 (4.1k 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 (891 points)
0 votes
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.
answered by Junior (719 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

42,514 questions
48,528 answers
155,014 comments
63,369 users