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?

- $h(n)$ is $O(f(n))$
- $h(n)$ is $O(g(n))$
- $g(n)$ is not $O(f(n))$
- $f(n)$ is $O(g(n))$

### 7 Comments

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 log_{2} 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.

## 10 Answers

$$\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.

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

### 21 Comments

f(n)= n, g(n) = 3n then f(n)= O(g) and we can also write g(n) = O(f) but more accurate ans is f(n) = theeta(g) reffer :https://dspace.mit.edu/bitstream/handle/1721.1/37150/6-046JFall-2004/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2004/CDF0CA1F-85EF-4FF4-933B-27E503A0AEA8/0/ps1sol.pdf

Both f(n) and g(n) are asymptotically equal. Caculcating log_{2} 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.

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.

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

@MRINMOY_HALDER @ankitgupta.1729 @srestha

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.

**Ans - D)**

**h = n!** , can also be written as

**h =** **n ^{n}** (a weak upper bound on the factorial function

**n! <= n**, as each of the n terms in the factorial product is at most n ).

^{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

@Harsh181996 sir

How n! can be written as n^n

2!=2

4!=24 but 4^4=256

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.