algorithmtime-complexityprobabilityconstant-time

Algorithm to find numerical bucket in dynamic list

Say I have input that looks something like this:

[
  {index: 0, probability: 0.20},
  {index: 1, probability: 0.10},
  {index: 2, probability: 0.40},
  {index: 3, probability: 0.25},
  {index: 4, probability: 0.05},
]

Given that I generate a random number [0,1), is there an O(1) algorithm that I can use to find which index of this array "matches" that probability?

The way I would do it in O(N) is to do something like:

let cumulative = 0;
const r = Math.random();
for(const v of list){
    cumulative += v.probability;
    if(r < cumulative){
      return v.index;
    }
}

I believe the O(N) algorithm is doing what I want, but not sure if there is a faster way?

Solution

  • Replace the list with cumulative probability:

    [
  {index: 0, probability: 0.20},
  {index: 1, probability: 0.30},
  {index: 2, probability: 0.70},
  {index: 3, probability: 0.95},
  {index: 4, probability: 1.00},
]

    Then do a binary search on probability to find the index. The complexity would be O(log N)