Algorithms doubt

Question

If f (n), g(n) and h(n) are non-decreasing complexity functions.

if f(n) ∈ O(h(n)), what is the  relation between  f(n)  and (g ◦ h(n) + c), for any constant c ≥ 0, where a ◦ b is the composite function of a and b.

A  f(n)  ∈ O(g ◦ h(n) + c),

B  f(n)  ∈ $\Theta$(g ◦ h(n) + c),

C  f(n)  ∈$\Omega$(g ◦ h(n) + c),

D  none

?

Comments

from my view :

f(n) = O(h(n))  ( i conclude this statement f(n) ∈ O(h(n))  )

which  is f(n) <= h(n) + c............................................................1

now for f(n)  and (g * h(n) + c),

as f(n) is already <= h(n) so if g is multiplied with it  will become bigger.. not smalller .

so i said option a.

 

IS IT RIGHT ?

---

g is not multilied it is composition of function

---

i updated answer as composition . now see...

Answer 1

okk  ( // g is not multilpied it is composition of function ) 

 

suppose  h(n)  = 3n^2 + c.

f(n) belongs to O (h(n)) .

so O (h(n) ) can be n ^2 , n^3 etc.....

suppose i fix f(n) as n^3

---

now take function (g ◦ h(n) + c)

so The composition of functions f : A → B and g : B → C is the function
gof : A → C given by gof (x) = g(f (x)) ∀ x ∈ A

so g(h(n) ) =g ( 3n^2 +2 )  which is appox. g( n^2 ).

i take two cases when g(n) < h(n) and 2nd g(n) > h(n)

so suppose g(n) = n  then it is g(n) = n ^2 .now O(g(n)) can be n^2 can be n^3 etc. means go some where in n we get it in worst case. so  f(n) belongs to O ( g. h(n) )

suppose g(n) = n ^3 

then g(n^2) = n ^6 then g(n ) is n^6 and f(n) is n^2 here so f(n) < g(n).

so i think it is option b.

Comments

is this correct?

---

 

In the problem it is given that f(n) ∈ O(h(n))   this means  for   

f(n) belongs to O(h(n)) not f(n) = O(h(n) , 

f(n) ∈ O(h(n))  this means f(n) >= h(n) .

---

 

one problem in my solution of h(n) = 1/n  as it is decreasing .

and we want non decreasing in h(n) so iwill update that