The algorithm processes one event per segment endpoint or crossing point, in the sorted order of the ''<math>x''</math>-coordinates of these points, as may be proven by induction. This follows because, once the ''<math>i''</math>th event has been processed, the next event (if it is a crossing point) must be a crossing of two segments that are adjacent in the ordering of the segments represented by ''<math>T''</math>, and because the algorithm maintains all crossings between adjacent segments as potential future events in the event queue; therefore, the correct next event will always be present in the event queue. As a consequence, it correctly finds all crossings of input line segments, the problem it was designed to solve.
The Bentley–Ottmann algorithm processes a sequence of 2''n''<math>2n + ''k''</math> events, where ''<math>n''</math> denotes the number of input line segments and ''<math>k''</math> denotes the number of crossings. Each event is processed by a constant number of operations in the binary search tree and the event queue, and (because it contains only segment endpoints and crossings between adjacent segments) the event queue never contains more than 3''n''<math>3n</math> events. Thus, allAll operations take time <math>\mathcal{O}(\log ''n'')</math>. andHence the total time for the algorithm is <math>\mathcal{O}((''n'' + ''k'') \log ''n'')</math>.
If the crossings found by the algorithm do not need to be stored once they have been found, the space used by the algorithm at any point in time is <math>\mathcal{O}(''n'')</math>: each of the ''<math>n''</math> input line segments corresponds to at most one node of the binary search tree ''T'', and as stated above the event queue contains at most 3''n''<math>3n</math> elements. This space bound is due to {{harvtxt|Brown|1981}}; the original version of the algorithm was slightly different (it did not remove crossing events from ''<math>Q''</math> when some other event causes the two crossing segments to become non-adjacent) causing it to use more space.<ref>The nonlinear space complexity of the original version of the algorithm was analyzed by {{harvtxt|Pach|Sharir|1991}}.</ref>
{{harvtxt|Chen|Chan|2003}} described a highly space-efficient version of the Bentley–Ottmann algorithm that encodes most of its information in the ordering of the segments in an array representing the input, requiring only <math>\mathcal{O}(\log<sup>^2 n)</supmath>''n'') additional memory cells. However, in order to access the encoded information, the algorithm is slowed by a logarithmic factor.
==Special position and numerical precision issues==
