Hi,

If we are looking for line intersections (horizontal and vertical lines only) and we have n lines with half of them vertical and no intersections then

Sorting the list of line end points on y value will take N log N using mergesort

Each insert delete and search of our data structue (assuming its a b-tree) will be < log n

so the total search time will be N log N

What am i missing here, if the time to sort using mergesort takes a time of N log N and insert and delete takes a time of < log n are we dropping the constant factor to give an overal time of N log N. If not then how comes < log n goes missing in total ONotation run time?

Thanks