Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Sparse Table Algorithm - Query Time should be O(log N) | Reply
I believe that we always need to compute the "k" described in the tutorial, which take time proportional to log(R-L),where [L,R] is the interval in which we do the RMQ. In worst case this could be log(N).

Thus i think the query time is O(log N). Am i wrong somewhere in my conclusion?
The bound described in the tutorial ignores this point.