Question 1209506: Consider the following algorithm:
while True:
i = random(1, n)
if a[i] == 1:
return i
The objective is to find a position in an array 𝑎[1..n] that contains the value 1, where half of the values in 𝑎 are zeroes and the other half are ones. The function random(1, n) returns a random integer between 1 and 𝑛.
How can I calculate the best, average and worst-case performance of this algorithm?
Answer by ikleyn(52890)   (Show Source):
You can put this solution on YOUR website! .
The best case performance is when "1" is in the first position in the array.
Then one step of the loop is just enough.
The worst case performance is when first half of the array is filled by zeroes,
while the second half is filled by ones.
Then n/2 steps of the loop is necessary.
The uncertainty arises, when ones and zeroes are distributed randomly in the array
Then any number of steps between 1 and n/2 may be needed.
This question reminds me one basic question of Philosophy:
if a glass is filled with water in half,
is it half-full or half-empty ?
The History knows examples when whole/entire states have disappeared
when they began to clarify such questions . . .
|
|
|
