I found this rule about algorithm analysis:
O(max{f(n),g(n)}) = O(f(n)+g(n))
How to prove this?
I know:
max{f(n),g(n)} <= f(n)+g(n) <= 2 * max{f(n),g(n)}
thus:
max{f(n),g(n)} is O(f(n)+g(n))
max{f(n),g(n)} is O(max{f(n),g(n)})
f(n)+g(n) is O(max{f(n),g(n)})
But then
If a is O(b) and b is O(a) then O(a) = O(b) ?
To prove that O(max{f(n),g(n)}) = O(f(n)+g(n)), we can use the formal definition of big-O:
f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that
|f(x)| ≤ M|g(x)| for all x ≥ x0.
The absolute value applied in this definition really is a theoretical issue, as in practice only functions are used in the big-O notation which always give positive values for large enough x. It makes no sense to specify a negative big-O complexity. So I will not use that absolute value in the rest of this answer, but assume the functions yield positive values.
For grasping the concept of big-O, it might be worth to read this short article about Big-O misconceptions.
Using the above definition, we can say of some function s(n):
s(n) is O(f(n)+g(n)) if and only if there is an M such that
|s(n)| ≤ M(f(n) + g(n)) for large enough n, which is equivalent to:
|s(n)| ≤ M·max{f(n), g(n)} + M·min{f(n), g(n)} for large enough n.
For that same M the following would then also be true -- here we depend on the assumption that both f(n) and g(n) are positive for large n:
|s(n)| ≤ 2M·max{f(n), g(n)} for large enough n.
If we now choose P to be 2M, then we can say we have a P for which:
|s(n)| ≤ P·max{f(n), g(n)} for large enough n.
...which according to the definition of big-O means that
s(n) is O(max{f(n), g(n)}) ∎
s(n) is O(max{f(n), g(n)}) if and only if there is an P such that
|s(n)| ≤ P·max{f(n), g(n)} for large enough n.
Because for positive numbers (cf. the assumption) max{f(n), g(n)} < f(n)+g(n), this implies that the following is certainly true (we increased the right hand of the inequality):
|s(n)| ≤ P(f(n) + g(n)) for large enough n.
...which according to the definition of big-O means that
s(n) is O(f(n)+g(n)) ∎
The above proves that if any function is O(f(n)+g(n)) then it must also be O(max{f(n),g(n)}), and vice versa. This is the same as saying that both big-O complexities are the same:
O(f(n)+g(n)) = O(max{f(n),g(n)})
Note that this is not about equality of functions, but equivalence of big-O expressions.
In fact, you could look at big-O expressions as sets of functions, i.e. sets of those functions that have corresponding big-O complexity. So then the above proves:
s(n) ∈ O(f(n)+g(n)) ⇔ s(n) ∈ O(max{f(n),g(n)})
and this means both O-sets are the same.
We need the (practical) assumption that both f(n) and g(n) are always positive for large enough n. They can be negative and/or undefined on some subsets of ℝ, but there must be an n above which f(n) and g(n) always yield a non-negative result. If this were not the case, then the premise can be proved false with a simple counter example:
g(n) = n
f(n) = -n
The premise O(max{f(n),g(n)}) = O(f(n)+g(n)) then becomes:
O(n) = O(0)
which evidently is false. This is because f(n) violates the assumption and is always negative for large n. But again, a negative complexity makes no practical sense.
To be clear: these big-O functions may be negative or even undefined on some subsets of ℝ. As long as there is an n above which they always yield a non-negative number, they are in line with the assumption.
Examples of allowable functions that yield negative results and/or are undefined on subset(s) of ℝ:
n
log(n)
n³
sqrt(n)
Examples of functions that violate the assumption:
sin(n)
cos(n)
tg(n)
-n