ajains's blog

Mo's algorithm definition not cleared

By ajains, history, 6 years ago, In English

Why do we take sqrt(N) as block size in algorithm suppose i take 5 as block size what would be the difference?

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
  Vote: I like it +25 Vote: I do not like it

We are given queries(expressed as [l,r] interval, 1<=l<=r<=n) and sort them with group number that l is in, if same sort with r. suppose number of groups is g and block size is b. (g * b == q)

We will answer query by moving left and right pointer, and we will count number of moves of each pointer. left pointer will move O(q * b) times.(worst when left pointer iterate whole block for each query) right pointer will move O(g * n) times. (worst when right cursor iterate whole sequence for each block that left pointer is at. Right pointer is only increasing when left pointer is in same block.)

we choose b = sqrt(n) so time complexity will be O((n+q) sqrt(n))

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    g * b == q if we maintain this we will be getting appropriate time complexity right?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      Actually g * b = n, since you turn the complete array into g groups of size b. (DongwonShin wrote q by accident.) And that's just a fact. Maintaining this will not give you the optimal complexity, but just making sure that the algorithm works at all.

      The most important thing is that by sorting the queries in the special way, the complexity will be O(q·b + g·n) (see DongwonShin's explanation).

      So the important question is, what is the optimal block size such that the algorithm will run the fastest.

      If you for instance pick 5 as block size, then you will have the complexity O(q·5 + n / 5·n) = O(n2), which will be pretty bad. Turns out that if q ≈ n, then the optimal choice is . This gives the total complexity .

      → Reply