# Is $O(T+\log T)= O(T\log T)$?

Is $$O(T+\log T)= O(T\log T)$$?

I think this is true but I do not know how to show it mathematically?

Please show it using the definition.

Also, if it is true, is the following true?

$$O((T+\log T)^{1/n})= O((T\log T)^{1/n})$$

• What makes you think it may be true? – Sandro Lovnički Dec 30 '18 at 19:09
• "Please show it using the definition." What definition are you talking about? I know at least three common ones for $O(\cdot)$. – dkaeae Dec 30 '18 at 19:16

Let $$b$$ be the base of the logarithm. If $$T > \max(b^2, 2)$$, then $$\log T =\log_b T> 2$$. So $$T\log T - (T+\log T) = (T-1)(\log T -1) -1 > 1\times 1 -1 =0$$ i.e., $$T+\log T< T\log T$$.
So, any function that grows asymptotically slower than $$T+\log T$$ modulo a constant factor also grows asymptotically slower than $$T\log T$$ modulo the same constant factor. According to the definition of multiple usages of big O-notation, $$O(T+\log T)= O(T\log T)$$
Yes, it is true that $$O((T+\log T)^{1/n})= O((T\log T)^{1/n})$$, where we consider $$n$$ as a constant.
• The last $1$ in the r.h.s of the first equality should be $-1$. It works for $t \geq 4$ when $\log$ is natural logarithm and $t \geq 15$ when the base is $10$. – Saeed Dec 30 '18 at 19:51
• @Saeed Note the abuse of notation here. While "O(n + log n) = O(n log n)" is wrong, mathematically speaking, "=" is often supposed to be read as "$\subseteq$" in this context. – Raphael Dec 30 '18 at 21:39
• @ Raphael: Good point. thank you. I didn't know that. Shall I use, say $O(n) \subseteq O(n+1)$ instead of $O(n) =O(n+1)$? – Saeed Dec 30 '18 at 22:26