Question: Say we have $f(n) = O(n)$ and $g(n) = O(n)$, Show (or not) that $f(n) + c g(k) = O(n+k)$
Solution:
We have : $f(n) = O(n) \Leftrightarrow \exists a \ \textrm{ and } \ n_0 \ \textrm{ s.t. } \ f(n) \leq a \cdot n \ \forall \ n \geq n_0$
and similarly: $g(k) = O(k) \Leftrightarrow \exists b \ \textrm{ and } \ k_0 \ \textrm{ s.t. } \ g(k) \leq b \cdot k \ \forall \ n \geq k_0$
so $$ f(n) + cg(k) \leq a\cdot O(n) + c \cdot b \cdot O(k) $$
But at this point I start thinking maybe the statement does not make sense, how could we have one algorithm running on two different input sizes. Any Hints would be much appreciated! Thank you!
For $n+k \ge n_0 + k_0$, you have
$$\vert f(n)+ c g(k) \vert \le \vert f(n) \vert + c \vert g(k) \vert \le an+cbk \le \max(a,cb)(n+k)$$
So indeed saying that $f(n) + c g(k) = O(n+k)$ makes sense using Big O notation.