acash's blog

Please help with Mos algo time complexity

By acash, history, 2 months ago, In English

Hi everyone I was reading article on mos algo from Mos algo. Let's say we have 1e5 and the queries are like (b1,bn) (b2,b3) (b4,bn) (b5,b6) (b7,bn). If we sort the queries according to Mos algorithm where bi represents the block number it seems that the left pointer will always be increasing However the right pointer is jumping between blocks (eg bn to b3, b3 to bn and bn to b6) Wouldnt the right pointer need O(n) time because if we want to go from bi to bn then we have traverse all the elements in all the blocks present between bi to bn Please help what i am getting wrong here ?

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

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

Auto comment: topic has been updated by acash (previous revision, new revision, compare).

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

figure it out yourself this is why you are gray lol

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Read the rev.1 of this comment if you don't understand the Mo's algorithm complexity.

In your example the additional $$$O(n)$$$ is given by switching block, not per query. And because your $$$q$$$ is too small, it's possible switch a block every query. However you only need to switch block for at most $$$O(\dfrac{n}{B})$$$ times no matter how much queries there are. It's impossible to construct more than $$$O(\dfrac{n}{B})$$$ queries in which the right pointer of each query belongs to a different block.

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for the reply Sir, It seems i got it. Since there are B blocks in total of B size. For each block we can have this jump of O(n) time, which will gives us n * B which is nsqrt(n) and also for left pointer which is only increasing it we will get overall O(n). So total O(n) + O(nsqrt(n))

    → Reply