Complexity Big O, little o

[ammoun]

Hi

When we have f(n) $\in$ o(g(n)) and g(n) $\in$ O(H(n))

Can I proove that h(n)-f(n) $\in$ o(g(n))?

Obviously I don't want you to give me the answer, but some hints and maybe which definitions of O and o I should use.

Thanks

 

[ammoun]

Ok, I believe I came up with a counter example:

If f(n)=n, g(n)=$n^{2}$ and h(n)=$n^{3}$

When I looked for the limit of the difference / g(n) it cannot give 0.

Could you please confirm this result?

Thanks

 

[ramsey2879]

Hi

When we have f(n) $\in$ o(g(n)) and g(n) $\in$ O(H(n))

Can I proove that h(n)-f(n) $\in$ o(g(n))?

Obviously I don't want you to give me the answer, but some hints and maybe which definitions of O and o I should use.

Thanks

What definitions are you talking about? Also how does H(n) relate to h(n). Forgive me for asking but I just don't know what you are referring to.

 

[ammoun]

What definitions are you talking about? Also how does H(n) relate to h(n). Forgive me for asking but I just don't know what you are referring to.

Thank you ramsey, it was the same function h and the definitions I'm talking about are of big O of a function and small o.

For example Big O of g(n) is the set of function f(n), f(n)≤c g(n). (not complete definition)

 

[blue_raver22]

Hello,

To prove that h(n)-f(n) \in o(g(n)), you can use the definition of little o notation, which states that for any positive constant c, there exists a positive integer n0 such that for all n > n0, |f(n)| < c|g(n)|. In other words, the rate of growth of f(n) is significantly smaller than that of g(n) as n approaches infinity.

To start, you can assume that h(n) and f(n) both belong to o(g(n)), meaning that for any positive constant c, there exists a positive integer n0 such that for all n > n0, |h(n)| < c|g(n)| and |f(n)| < c|g(n)|. Now, you can use these two inequalities to show that |h(n)-f(n)| < c|g(n)| for all n > n0. This will prove that h(n)-f(n) also belongs to o(g(n)).

I hope this helps. Best of luck with your proof!