5.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))$
edited | 5.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.

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

$\begin{array}{|l|l|l|}\hline \text{} & \text{n= 256} & \text{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.

edited ago
+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.
0

@Arjun sir

Can we say $n! \leq O(n^{n})$

0

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!

0
0
thanks Puja!
0
Here h(n)>f(n)>g(n)

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

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

0

@Krushna Kotgire

see Arjun sir explanation D is answer

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.

0

@Harsh181996 sir

How n! can be written as n^n

2!=2

4!=24 but 4^4=256

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 :-)
+1 vote
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.

option d is correct.

edited

1
2