search
Log In
0 votes
117 views

f(n)=O(g(n))

Which of the following is True?

  1. 2^f(n)=O(2^(g(n))
  2. log(f(n))=O(log(g(n))
  3. f(n)=O(f(n/2))
  4. f(n)=O(f(n)^2)
in Algorithms 117 views
0
answer is B but can someone help me to how to solve these questions with 100% accuracy because i'm always trying to find counterexample and don't know a formal way to solve
0

@Mk Utkarsh could you please share your solution, I am a bit confused between D and B

1
let $f(n) =\frac{1}{n}$

$(f(n))^2 = \frac{1}{n^2}$

$f(n) \neq O(\frac{1}{n^2})$

So D is incorrect and i'm not able to find counter example of B
0
B is the correct answer bro!

1 Answer

0 votes

Related questions

0 votes
2 answers
1
246 views
What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$
asked Mar 30 in Algorithms Lakshman Patel RJIT 246 views
4 votes
4 answers
2
465 views
Among the following asymptotic expressions, which of these functions grows the slowest (as a function of $n$) asymptotically? $2^{\log n}$ $n^{10}$ $(\sqrt{\log n})^{\log ^{2} n}$ $(\log n)^{\sqrt{\log n}}$ $2^{2^{\sqrt{\log\log n}}}$
asked Feb 11 in Algorithms Lakshman Patel RJIT 465 views
0 votes
1 answer
3
247 views
How to check if a given recurrence relation is in a format that is valid to apply Master’s Theorem? Also, how to distinguish between Master’s Theorem and extended Master’s Theorem?
asked Jun 12, 2019 in Algorithms lolster 247 views
1 vote
2 answers
4
449 views
If $T1(n) = \Theta(f(n))$ & $T2(n) = \Theta(f(n))$ Then, Is $T1(n) + T2(n) = O(f(n))$ If yes, then how?
asked May 26, 2019 in Algorithms shubhojit1412 449 views
...