Prove/disprove these two claims

  • Thread starter Thread starter Melodia
  • Start date Start date
Click For Summary

Homework Help Overview

The discussion revolves around understanding two claims related to the Big O notation in the context of functions, specifically focusing on the implications of the order of functions f and g when combined.

Discussion Character

  • Conceptual clarification, Assumption checking

Approaches and Questions Raised

  • Participants explore the definitions of Big O notation and question the implications of combining functions f and g. There is a discussion about whether the positivity of functions affects their order and the interpretation of the claims.

Discussion Status

The conversation includes attempts to clarify definitions and implications of the claims. Some participants suggest that a proof by contradiction may be a viable approach, while others express uncertainty about the conditions under which the claims hold true.

Contextual Notes

There is a focus on the definitions and constraints of the functions involved, particularly regarding their positivity and the implications of the notation used in the claims.

Melodia
Messages
18
Reaction score
0

Homework Statement


I'm having trouble understanding this pair of claims:
cDMJw.jpg



Homework Equations





The Attempt at a Solution



So g is some function whose result is greater or equal to 0... but I don't really get what the rest of the claim means.
Could someone please explain them to me?
Thanks in advance.
 
Physics news on Phys.org
[tex]\mbox{ If } f(n)= O(g(n)), \mbox{ then it means that the function f(n) is of order at most g(n)}.[/tex]

[tex]\mbox{ That is, by def., f(n) is big oh of g(n) if ther exists some positive constant C such that}[/tex]

[tex]|f(n)|\leq C|g(n)|[/tex]

Considering this, then what the problem is asking is that if f+g is of order at most h, then each of f and g must be of order at most h.

I haven't worked any of these problems out myself, but a proof by contradiction looks promising.
 
Ok thanks for clearing it up.
So basically it's saying:
If f(n) + g(n) [tex]\leq[/tex] c[h(n)]
Then f(n) [tex]\leq[/tex] c[h(n)] and g(n) [tex]\leq[/tex] c[h(n)]
The tricky part is that f(n) could be negative right? Since it says "[tex]\forall[/tex] f". Then f(n) could be larger than (f + g)(n)? Or does "[tex]\forall[/tex] f, g [tex]\in[/tex] F" mean "for all f and g that are in F"?
 
Last edited:
Look at the definition of f:N-->R+. Yes ti means for all f, g that are in F.
 
Oh ok, then the answer would be obvious right? I mean if both f and g has to be positive, then either f or g has to be smaller than f + g; then they have to be in O(h) as well.
 

Similar threads

  • · Replies 7 ·
Replies
7
Views
2K
Replies
5
Views
2K
  • · Replies 9 ·
Replies
9
Views
3K
  • · Replies 13 ·
Replies
13
Views
1K
Replies
9
Views
3K
Replies
4
Views
2K
  • · Replies 2 ·
Replies
2
Views
1K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 9 ·
Replies
9
Views
2K