Siriuslight's blog

Time complexity of Sparse table query
By Siriuslight, history, 7 years ago, In English

I am little confused on time complexity of a query in sparse table. I got conflicting answers from two sources. On hackerearth O(logn) (link) is mentioned and on geeksforgeeks O(1) (link) is mentioned.

Can anyone tell me the correct time complexity?

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

If your query will not be affected with overlapped ranges like RMQ (i.e RMQ in range [1, 10] is the same of min( RMQ[1, 6], RMQ[4, 10]) ), then you can solve it in O(1). But if your query will be affected with overlapped ranges like Range Sum Query, then you have to solve it in O(log(n)) as mentioned in hackerearth like.

→ Reply