Multiplying Big-Os

Question

I've seen the following in a text:

$\mathcal{O}(\sqrt{n})\cdot \mathcal{O}(n\log n)$

How is that even defined?

Ok, I guess one can replace it with:

$\mathcal{O}(\sqrt{n} \, n\log n)$

Is that right?

Answer 1

Suppose that $f \in (\sqrt n)$ and $g \in O(n \log n)$. Pedantically, this means that there are constants $c_f$, $c_g$, $N_f$, $N_g$ such that

1. For all $n > N_f$, $\lvert f(n)\rvert < c_f \sqrt n$, and
2. For all $n > N_g$, $\lvert g(n) \rvert < c_g n \log n.$

Call $N = \max\{ N_f, N_g\}$ and $c = c_f c_g$. Then it is also true that for all $n > N$, $\lvert f(n)\rvert < c \sqrt n$ and $\lvert g(n)\rvert < c n \log n$, and thus it's true that $fg \in O(n\sqrt n \log n)$.

We've shown that it does make sense to talk about $O(\sqrt n) \cdot O(n\log n)$, and the result is $O(n \sqrt n \log n)$ as expected.

Answer 2

Let $T_1(n) \leq c_1 \sqrt n$ and $T_2(n) \leq c_2 n \log n$. Now, $$ T(n) = T_1(n) \times T_2(n) = c_1 c_2 \sqrt n n \log n = O(n^{1.5} \log n)$$

Remarks : In the last step one can think of a constant $c = c_1 c_2$.