Algorithms timeComplexity

Question

It answer is given as A but according to me answer should be C.

Please help 

Comments

f(n)=1/n g(n)=1

f(n)<*g(n)

2^1/n>=1

 

---

For x <= y, I can write n^x = O(n^y) . eg n² = O(n³ ) also for '=' ---  n² = O(n² ) according to Big-O definition.

Definition of Big-O says f(n) <= cg(n) for c>0 and n>n₀ , then I can write f(n) = O(g(n)), Hence I can say first one is true.

Statement 2 is True, it's a property. Even we can apply log on both sides.

Hence, both statements are true and answer should be C.

---

sakharam  please elaborate more !

 

---

@Swapnil Naik

it's a property. Even we can apply log on both sides.

can you provide some reference

---

According to the example given by Dharmendra I am sure that property is false. I thought it's true because we can take log on both sides like how we find a function which has greater complexity, but later I realized even that is not true

https://gateoverflow.in/91704/asymptotic-complexity

Please correct me If I am wrong

if f(n) = O(g(n)) then

I) 2^f(n) = O(2^g(n))

II) log(f(n)) = O(log(g(n)))

These both statements are false right?

 

 

---

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

=> f(n) <=g(n)   [ means f(n) should be g(n) or less than g(n) ]   [1 ,2, 3, 4 .........g(n) max ]

=>f(n)/g(n) <=1

 2^f(n) = O 2^g(n)

2^f(n) <= 2^g(n)

2^f(n)-g(n) <=1

2⁰ <= 1 [when f(n) = g(n)]

2^-1 <=1 [when f(n) = g(n)-1]

2^-2 <=1     [when f(n) = g(n)-2]

......

2^_1-g(n)  <=1

therefore, condition is hold true  

option C is right

---

@Magma

https://math.stackexchange.com/questions/1482733/big-o-if-fn-ogn-prove-2fn-o2gn

 

@Swapnil Naik

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

---

@Shaik

Here answer should be D)

rt?

because take counter

in 1) take n=1/x

if x=2 and y=3

then $\frac{1}{x^{2}} >\frac{1}{x^{3}}$

---

@srestha, mam

you can't substitute something in place of n

given that,

if 0 ≤ x ≤ y then n^x = O(n^y) --------------- give such x,y which is false.

---

can you give some example in against of 2  statement

---

@Shaik

why n cannot be substituted?

---

mam, you are inversing the n ===> for getting correct result, your result should be inverse

Answer 1

we know statement 1 is true.

statement 2:

f(n)=2n

g(n)=n

then f(n)=O(g(n)) but

2^f(n) $\neq$ O(2^g(n))

i.e. Answer : A

Comments

This looks good