vishudon's blog

Can inversion count problem be solved in O(n+k) where n <= k <= (n*n) ?
By vishudon, history, 4 years ago, In English

Dear community,

I hope you all are doing good and safe. I just want to know one thing. Recently I had a interview and the interviewer asked one question, how to solve inversion count problem.

I suggested two approaches to him (1. brute force, and 2. using merge sort). He was completely satisfied by my both the approaches.

But at last, he asked one question to me. Can we solve inversion count problem in O(n+k) where n <= k <= (n*n) ?

I couldn't suggest such approach to him. Also, my bad luck, I couldn't ask him about such approach. But, I am just curious to know is this really possible ? Can someone suggest some approach which could solve inversion count problem in O(n+k) where n <= k <= (n*n) ?

Thanks.

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

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

Yes, it’s kinda similar to the bubble sort. At each step add element to the end of the array and move it to the left until it will end at the good position.

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

    That has a name and it's insertion sort.

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

If $$$k = n \cdot n$$$, isn't it the same as the bruteforce bubble sort approach?

→ Reply