Prove/disprove these two claims

  • Thread starter Thread starter Melodia
  • Start date Start date
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
\mbox{ If } f(n)= O(g(n)), \mbox{ then it means that the function f(n) is of order at most g(n)}.

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

|f(n)|\leq C|g(n)|

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) \leq c[h(n)]
Then f(n) \leq c[h(n)] and g(n) \leq c[h(n)]
The tricky part is that f(n) could be negative right? Since it says "\forall f". Then f(n) could be larger than (f + g)(n)? Or does "\forall f, g \in 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.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top