1
$\begingroup$

Is it true that $O(k(n) + m(n))$ is equal to $O(\max\{k(n), m(n)\})$? In one of papers on computational complexity I've found the following statement:

$$O(\log(n) + n(\log S + \log V )) = O(n(\log S + \log V )).$$

Does it follow from the equality given above?

The only similar proof I know is: For $f_1(n) ∈ O(g_1(n))$ and $f_2 ∈ O(g_2(n))$, $f_1(n) + f_2(n) ∈ O(\max\{g_1(n), g_2(n)\})$. I'm almost sure they are related, but for some reason it's not completely clear to me. Thanks for help.

$\endgroup$
1
$\begingroup$

To see your property, take $g_1 = f_1$ and $g_2 = f_2$ in your known theorem. Then your conjecture holds. Or you can see it as follows. Clearly $O(\max(f_1,f_2))$ is no greater than $O(f_1 + f_2)$, and $O(f_1 + f_2)$ is no greater than $O(2 \max(f_1,f_2))$.

$\endgroup$
1
$\begingroup$

Yes.

It's not hard to prove. Let $f(n)\in \mathcal{O}(F(n)), g(n)\in \mathcal{O}(G(n))$, and say the bounding is explicitly

$$|f(n)|\le C_f F(n),\quad |g(n)|\le C_g G(n)$$

for constants, $C_f,C_g>0$. Then

$$|f(n)+g(n)|\le |f(n)|+|g(n)$$ $$\le C_fF(n)+C_gG(n)$$

setting $M=\max\{C_f,C_g\}$ we see this is

$$\le M(F(n)+G(n))$$

$$=M\bigg(\max\{F(n),G(n)\}+\min\{F(n),G(n)\}\bigg)$$

$$\le M\bigg(\max\{F(n),G(n)\}+\max\{F(n),G(n)\}\bigg)$$

$$=2M\max\{F(n),G(n)\}$$

so by definition $(f+g)(n)\in \mathcal{O}\left(\max\{F(n), G(n)\}\right)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.