retagged by
742 views
5 votes
5 votes

For which of the following functions $f(n)$ and $g(n),$ it holds $:f(n)=O(g(n)).$ Every $\log$ below is base $2.$

  1. $f(n)=2^{k \log n}\;, \quad g(n)=n^k$
  2. $f(n)=2^n\;, \quad g(n)=2^{2 n}$
  3. $f(n)=\left\{\begin{array}{ll}4^n & \text { if } n<2^{1000} \\
    2^{1000}\; n^2 & \text { if } n \geq 2^{1000}\end{array}\;, \quad g(n)=\dfrac{n^2}{2^{1000}}\right.$
  4. $f(n)=2^{\sqrt{\log n}}\;, \quad g(n)= (\log n)^{100}$
retagged by

1 Answer

1 votes
1 votes

Answer: Option A,B,C

A)

 

 

B) 

 

C)

 

​​​​​​​D)

​​​​​​​

 

Answer:

Related questions

2 votes
2 votes
1 answer
2