Is h(n) - f(n) in o(g(n)) Given f(n) in o(g(n)) and g(n) in O(H(n))?

  • Context: Graduate 
  • Thread starter Thread starter ammoun
  • Start date Start date
  • Tags Tags
    Complexity
Click For Summary

Discussion Overview

The discussion revolves around the relationship between functions in asymptotic notation, specifically whether h(n) - f(n) is in o(g(n)) given that f(n) is in o(g(n)) and g(n) is in O(H(n)). Participants explore definitions and seek clarification on the implications of these relationships.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant questions whether h(n) - f(n) can be proven to be in o(g(n)) under the given conditions.
  • Another participant proposes a counterexample with specific functions f(n) = n, g(n) = n², and h(n) = n³, suggesting that the limit of the difference divided by g(n) does not approach 0.
  • Clarifications are sought regarding the definitions of big O and small o, as well as the relationship between H(n) and h(n).
  • Definitions of big O and small o are discussed, with one participant providing an incomplete definition of big O.

Areas of Agreement / Disagreement

Participants express uncertainty about the implications of the relationships between the functions, and there is no consensus on whether h(n) - f(n) is in o(g(n)).

Contextual Notes

There are limitations in the discussion regarding the completeness of definitions and the relationship between H(n) and h(n), which remain unresolved.

ammoun
Messages
5
Reaction score
0
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
 
Physics news on Phys.org
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
 
ammoun said:
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.
 
ramsey2879 said:
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)
 

Similar threads

Undergrad Meaning of terms in a direct sum decomposition of an algebra
  • · Replies 8 ·
Replies
8
Views
3K
Undergrad Dfns group action & group, written in terms of the other
  • · Replies 26 ·
Replies
26
Views
1K
MHB Why is the order of b equal to the order of G/H ?
  • · Replies 6 ·
Replies
6
Views
2K
MHB Show that G is a subset of the symmetric group
  • · Replies 7 ·
Replies
7
Views
2K
Graduate Decomposition into irreps of compact Lie group
  • · Replies 4 ·
Replies
4
Views
992
Undergrad Trouble with a passage in Zariski & Samuel's Commutative algebra text
  • · Replies 5 ·
Replies
5
Views
2K
High School Transformation Rules For A General Tensor M
  • · Replies 1 ·
Replies
1
Views
2K
MHB Which of the group axioms are satisfied?
  • · Replies 9 ·
Replies
9
Views
2K
MHB Kernel of Linear Map $\theta$ in $\mathbb{F}_{q^n}$
  • · Replies 24 ·
Replies
24
Views
4K
Comp Sci Proofing Big-O Notation: O(max(f(n), g(n)))
  • · Replies 4 ·
Replies
4
Views
3K