60.0k views
0 votes
In class, we discussed an algorithm which allows us to query an interval i in a search tree S, and we receive an interval in S which overlaps with i if one exists. Using the algorithm discussed in class as a sub procedure, give an algorithm which returns every interval in S which overlaps with i. Suppose there are k such intervals. What is the worst case running time of your algorithm in terms of k and n

1 Answer

5 votes

Answer:

Step-by-step explanation:

The algorithm is expressed as S:

Count = array of k + 1 zero

For s in input do

count {key (s) } + = 1

total = 0

For i in 0, 1, ........ k do

count (i), total = total, count (i) + total

Output = array of the sum length input for s in input do

Output {count (key (s) } = s

count {key (s) } + = 1

return output

b) The total space usage of the algorithm can be an impediment for maximum key values that are significantly smaller.

User Ollie In PGH
by
8.1k points

No related questions found