code_warrior's blog

By code_warrior, history, 7 months ago, In English

I recently read the tutorial on MO's algorithm and found that the time complexity of mo's algorithm is O(q*(n/k)+n*k) where k is the block size and q is the number of queries. But ,how can it be so? For example- If i take q=2 and the ranges to be [1,n] and [n-1,n]. Then ,obviously the left pointer will have to move approx n cells and not q*sqrt(n) which is 2*sqrt(n). Please ,someone clarify my doubt!

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Remember that Big O notation cares only about asymptotic complexity (i.e. input is large). Increase your values of N and Q. What do you notice?