2
$\begingroup$

$\max(f(n), g(n)) = O(f(n) + g(n))$

How do I prove this? Also I'd appreciate the markup being corrected, thanks.

  • 0
    I've never seen the notation O(f(n),g(n)), what does it mean for you?2010-11-14
  • 0
    @Yuval Filmus: Thanks, that was an error. I've corrected it.2010-11-14

1 Answers 1

3

You can use $\max(f(n),g(n)) \leq f(n) + g(n)$, given that both functions are non-negative.

  • 0
    Does this still hold now that I've changed the operator used?2010-11-14
  • 0
    @Matt: Now it's immediate.2010-11-14