## Geometric Applications of BST quiz

What is the worst case number of compares to perform a 1d range count if the keys are stored in an ordered array and the 1d range search is performed efficiently?

linearithmic
linear
constant
logarithmic

What is the worst case running time of the sweep-line algorithm to find all R intersections among N orthogonal line segments?

constant + R
log N + R
N log N + R
N log N + R log N

Suppose that the keys are stored in a sorted array. What is the order of growth of the running time to perform range count as a function of N and R ? (N=number of keys and R- number of matches)

log N
log R
log N + R
N + R

Suppose that the points [(3, 3), (1, 5), (4, 4), (5,4), (3, 2), (4, 2) ] are inserted into a 2D Tree in that order. Which of the following statement is true?

The point (5,4) is inserted to the left of (4,4)
The point (3,2) is inserted to the right of (1,5)
The point (4,2) is inserted to the left of (5,4)
The point (4,2) is inserted to the right of (3,2)