The Bentley–Ottmann algorithm, for example, has time complexity of $O((n + k) \log n)$. Is the statement $O((n + k) \log n) = O(n \log n)$ true? I know that $k$ is there because it has big enough of an impact on the overall time complexity that it's relevant to include it. But can it be ignored, so that the previously stated equivalence holds, and hence we can without any reservations say that the algorithm has time complexity of $O(n \log n)$?


In general you cannot erase things. A bivariate function $f$ is $O((n+k)\log n)$ if there exists a constant $C>0$ such that for all legal settings of the parameters $n,k$, we have $f(n,k) \leq C(n+k)\log n$. Here a setting of parameters is legal if it can actually happen – for example, if $V,E$ are the number of vertices and edges in a simple graph, then we always have $E \leq V(V-1)/2$, any other setting being illegal. If in some context you know that $k \leq Bn$, then in that context (which restricts the set of legal settings of parameters) $f = O(n\log n)$. In any other context, you cannot drop the $k$.

In your particular case, the Bentley–Ottmann algorithm, it is generally not the case that $k = O(n)$, and so $k$ cannot be dropped.

| cite | improve this answer | |
  • $\begingroup$ Just to be clear: if I'm looking for a $O(n \log n)$ algorithm, Bentley–Ottmann (as is, without domain specific modifications) would definitely fall out of the question? $\endgroup$ – user2340939 Jul 1 '17 at 21:59
  • 1
    $\begingroup$ Unless in your case you are guaranteed that $k = O(n)$. $\endgroup$ – Yuval Filmus Jul 1 '17 at 22:15
  • $\begingroup$ Could you answer this related question? cs.stackexchange.com/questions/77458/… $\endgroup$ – user2340939 Jul 1 '17 at 23:45

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.