1
$\begingroup$

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})$

$\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
2
$\begingroup$

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.

$\endgroup$
7
  • $\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

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.