Cerrar
Define the Range Minimum Query Problem i.e what does an RMQ return?
Describe the preprocessing for the Block Decomposition Algorithm for RMQs (Solution One)
Describe how a query is performed for the Block Decomposition Algorithm for RMQs.
With the Block Decomposition algorithm, describe why the query time is O(logn)
What is the time and space complexity for the Block Decomposition algorithm?
Explain the preprocessing stage of the 'Solution 2' algorithm for RMQs.
How much total space is used by the 'solution two' algorithm for RMQs?
How do we compute RMQ(i , j) if the interval length l = (j - i + 1) is not a power of two?
Using the 'Low Resolution RMQ' algorithm for RMQs. What time complexities can we expect?
