I've been working on a SkipList implementation in Java for my CS2 class, and after analyzing the runtime of all my methods (for fun), I had a problem identifying the average runtime of the following:
// Returns 1 with 50% probability, 2 with 25% probability,
// 3 with 12.5% probability, and so on, without exceeding maxHeight
private static int generateRandomHeight(int maxHeight)
{
int height = 1;
// At most O(maxHeight) which is O(log(n))
// Best case is O(1) and on average O(log(log(n)))??
while (--maxHeight > 0 && Math.random() < .5)
height++;
return height;
}
I know that the best runtime is O(1) and the worst runtime is O(h), which is guaranteed to be O(log(n)), since h = ⌈log₂(n)⌉ (ceiling of log base two of n).
Question is, what is the average expected runtime of this function?
At first glance, I assumed that it is expected to be O(log(log(n))). I brought this question to my TAs and after discussing with them, we are leaning on an average runtime of O(1), since it's most likely that we iterate only once or not at all (e.g 50%).
Aucun commentaire:
Enregistrer un commentaire