B-Tree Revision
- by stan
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