14,834 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))$

can any one answer this. These types of questions always confuse me.
I think option b and d are correct
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 ?
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.

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.

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

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

by

edited
Also,

f(n)=theta(g(n))
iff f(n)=0(g(n))
and
f(n)=omega(g(n))
No. Both f(n) and g(n) are O ( big oh) of each other. Hence answer is absolutely correct. Wats the confusion?
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.

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.

@ 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??
edited
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.
sir can uh pleas explain how the factorial has higher growth rate than exponential.1?? i am not getting
@Arjun sir

How is n multiplied √n times equivalent to √n multiplied n times? Take n=9 for counter example.

@Arjun sir

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

@MRINMOY_HALDER

Is $3n^{\sqrt{n}}$ asymptotically different from $n^{\sqrt{n}}$??

How is it different??

No, it's not. 3 is a constant
Can you tell me, then according to u how D) could be ans?? Check option C) too, how is it false??

@ankitgupta.1729 check it

mam, here, $f(n)= 3n^{\sqrt n}$ and $g(n)=n^{\sqrt n}$

Now, Is $f(n)=O(g(n)) ?$

To answer this, we have to find, Is there any positive constant 'c' such that $f(n) <= cg(n)$ for large 'n'

So, $3n^{\sqrt n} <= c*n^{\sqrt n}$...So, there exist a positive constant 'c' i.e. 'c' can be 3,4,5,...

So, we can say $f(n)=O(g(n))$ is true.

Now, Is $g(n)=O(f(n)) ?$

To answer this, we have to find, Is there any positive constant 'c' such that $g(n) <= cf(n)$ for large 'n'

So, $n^{\sqrt n} <= c*3n^{\sqrt n}$ $\Rightarrow c >=\frac{1}{3}$, So, here a positive constant 'c' also exists.

So, $g(n)=O(f(n))$ is true.

Since, $f=O(g)$ and $g=O(f)$. So, $f=\Theta(g)$ or $g=\Theta(f)$

@ankitgupta.1729

If asymptotically both are equal, then we can represent it by $O,\Omega, or \Theta$

anyone of these three. right??

mam, 2 functions $f(n)$ and $g(n)$ are asymptotically equal i.e. $f(n) \sim g(n)$ if  $\lim_{n\rightarrow \infty } \frac{f(n)}{g(n)} = 1$ . intuitively it is like $f(n)=\Theta (g(n))$ but I am not sure whether it is correct or not.

if we take log for all, then

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

g(n) = $\sqrt{n} \log (n)$        (base2)

h(n) = $n \log (n)$

Now, f(n)=g(n) <h(n)

Is this is correct ?

Simply, factorial function has higher growth rate than exponential. So, (A) and (B) are wrong.

Asymptotically, $f(n) = g(n) = \sqrt{n}log_2n$ (This can be proved by taking log both side of f(n) and g(n).

Hence, we can say either $f(n)\ is\ O(g(n))$ or $g(n)\ is\ O(f(n))$.

So, option (D) is right choice.

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!

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

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

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

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

1 comment

edited

@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 :-)

option d is correct.

1 comment

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

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

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

Refer below image

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