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})$
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ What makes you think it may be true? $\endgroup$ – Sandro Lovnički Dec 30 '18 at 19:09
-
1$\begingroup$ "Please show it using the definition." What definition are you talking about? I know at least three common ones for $O(\cdot)$. $\endgroup$ – dkaeae Dec 30 '18 at 19:16
Add a comment
|
$\begingroup$
$\endgroup$
7
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.
-
$\begingroup$ 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$. $\endgroup$ – Saeed Dec 30 '18 at 19:51
-
$\begingroup$ Sorry for my typo. I updated my answer (without seeing your comment.) $\endgroup$ – John L. Dec 30 '18 at 19:53
-
2$\begingroup$ @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. $\endgroup$ – Raphael♦ Dec 30 '18 at 21:39
-
$\begingroup$ @ 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)$? $\endgroup$ – Saeed Dec 30 '18 at 22:26
-
$\begingroup$ Both are fine, while the former might be easier to accept. You may want to check this question, O(·) is not a function, so how can a function be equal to it?, which has several nice answers. @Raphael's comment above is along the line of most popular answers over there, while my answer over there emphasizes a different perspective of the situation. $\endgroup$ – John L. Dec 31 '18 at 0:06
