Calculate big O notation

Question

I'm a bit unsure how to determine the big O notation of the following terms:

$\sqrt n\ $ + $\log n\ $

Is the big O notation O($\sqrt n\ $) or O ($\sqrt n\ $ + $\log n\ $)?

It's clear that $\sqrt n\ $ grows faster than $\log n\ $ but I'm uncertain, if it's enough to express that with O($\sqrt n\ $).

Thanks in advance!

Answer 1

If you think of $\mathcal O(\sqrt n)$ and $\mathcal O(\sqrt n + \log n)$ as sets of functions, they are exactly the same set. Thus, saying that the function $\sqrt n + \log n$ is $O(\sqrt n)$ is true, but saying that it is $O(\sqrt n + \log n)$ is also true. Typically, though, the former is preferred, since it's the simpler expression.

Answer 2

It's enough to say $\sqrt{n} + \log n = O(\sqrt{n})$. Notice that $\log n \le \sqrt{n}$ then $\sqrt{n} + \log n \le 2 \sqrt{n}$. More generally, if you have a sum $a_n + b_n$ and $\frac{a_n}{b_n} \to 0$ when $n \to \infty$ then $a_n + b_n = O(b_n)$. You can think of this as the largest asymptotic term wins.