SOLUTION: 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 contai
Algebra.Com
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(52908) (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 . . .
RELATED QUESTIONS
Given an array 𝑎[1..𝑛] containing half zeros and half ones, we need to find a... (answered by CPhill,ikleyn)
Give a postcondition for the following algorithm that completely describes how the final... (answered by solver91311)
Credit cards companies use an algorithm for distinguising between valid credit card... (answered by Edwin McCravy)
The Greedy Algorithm is an algorithm that would help us to find a Hamiltonian circuit in... (answered by ikleyn)
I experience an experiments 2 times (experiments A and B) now I want to know which one is (answered by stanbon)
Consider the n × n matrix A where
a(ij) [ 1 if i+j is even,
[ 0 if i+j is odd.
(answered by ikleyn)
I am trying to find out if these are true:
{{{(1 + i) / sqrt (2) = sqrt (i)}}}
and... (answered by venugopalramana)
Could someone please check my work on the following paragraph proof? This is to show why (answered by robertb)
Taking an algorithm course and working a union-find problem. Algebra & trig too long ago (answered by ikleyn)