Complexity Big O, little o

  • Thread starter ammoun
  • Start date
  • #1
5
0

Main Question or Discussion Point

Hi

When we have f(n) [itex]\in[/itex] o(g(n)) and g(n) [itex]\in[/itex] O(H(n))

Can I proove that h(n)-f(n) [itex]\in[/itex] 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
 

Answers and Replies

  • #2
5
0
Ok, I believe I came up with a counter example:

If f(n)=n, g(n)=[itex]n^{2}[/itex] and h(n)=[itex]n^{3}[/itex]

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

Could you please confirm this result?

Thanks
 
  • #3
841
0
Hi

When we have f(n) [itex]\in[/itex] o(g(n)) and g(n) [itex]\in[/itex] O(H(n))

Can I proove that h(n)-f(n) [itex]\in[/itex] 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.
 
  • #4
5
0
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)
 

Related Threads on Complexity Big O, little o

Replies
6
Views
14K
Replies
1
Views
2K
  • Last Post
Replies
7
Views
6K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
5
Views
10K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
2K
Replies
22
Views
4K
Replies
11
Views
5K
Replies
19
Views
8K
Top