_aditya's blog

Find the position of element.
By _aditya, history, 5 years ago, In English

Lets say we have a running stream of numbers. We have to insert each element to a sorted list, before inserting we have to find the position of element in list. The only way I know to do it efficiently is augmenting a AVL tree. And also there are policy based data structures. do you know some algorithm that can do this in logn?

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

Comments Comments (9)
| Write comment?
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

You can do it in $$$O(nlog n)$$$ by keeping a BIT that stores frequency of elements, if the elements are not too large.

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

    Why it is $$$O(n\log^2n)$$$? Isn't it $$$O(n\log n)$$$?

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

      We have one $$$O(logn)$$$ factor from binary search and one from fenwick tree.

      How will you do it $$$O(nlogn)$$$ otherwise?

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

I think there is a O(n logn) method which is to use an unordered map to discretize. (may have large constant factor)

Then we use a fenwick tree to see how many elements are placed in front of a certain index.

But that's assuming that you can preprocess your stream of numbers

→ Reply