Asymptotic

Question

Comments

A is false

---

A) False

B)

C) True

D) False

---

@Magma

i want explanation !

why C is true?

why D is false? 

---

Option  D is nicely explained by Arjun sir :  https://gateoverflow.in/12928/%24-log-and-log-log-are-polynomially-bounded-anybody-can-prove

Option C :  lets  assume  f(n) = O(n) [f(n) <= n : So ,f(n) should be either 'n' or less than 'n']

                      g(n) = O(n)  [g(n) < = n : so ,  f(n) should be either 'n' or less than 'n']

it's given that

f(n) + O(g(n)) = theta (f(n))

f(n) + O(O(n)) = theta (f(n))  since O(O(n)) = O(n)

f(n) + O(n) = theta (f(n))

 (1<=f(n)<=n ) + n  = theta (f(n))

therefore the range  LHS  should be "n" it's not less than 'n' nor more than n 

but In RHS there's f(n) and we know that ,f(n) should be either 'n' or less than 'n

 

lets take h(n) =  (1<=f(n)<=n ) + n

therefore  we can write = h(n) >=  f(n)

                                  = h(n) = omega(h(n))

therefore , C is false

 I know that I'm taking many assumptions in this question ... and also I'm not sure that this is a correct approach  or not

sorry

Deepalitrapti  can you post the answer ???

 

 

---

I THINK MAYBE OPTIONS OF B AND C ARE INTERCHANGED

as no g(n) need in 2nd one ,,still in the prove part.

and in 3rd we need g(n) part but no g(n)

---

NOT GETTING C CONCEPT .............

WHAT IS THE RELATION BETWEEN f(n) AND g(n)??

means f(n) can  be n!  and g(n) can be just O(n) they are independent from my view.

so this condition not necessarily true

---

@Magma

Arjun sir explanation leads to Option D is true, but you commented it is false.

---

 Shaik Masthan  , check carefully 

 ( login)! Is  unbounded function 

And (loglogn)! is bounded function 

---

@Magma

it's my mistake.

---

How can you prove option "c" without any actual value of the function g(n)? g(n) determines is the condition holds or not,i mean O(g(n)) it can be anything ?