Question_bank

Question

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

Which of the following is True?

• A. 2^f(n)=O(2^(g(n))
• B. log(f(n))=O(log(g(n))
• C. f(n)=O(f(n/2))
• D. f(n)=O(f(n)^2)

Comments

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

---

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

---

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

---

B is the correct answer bro!

Answer 1

May be below link will help you

https://cs.stackexchange.com/questions/42764/if-fn-ogn-then-is-logfn-ologgn