Given below is a randomized algorithm for searching for a value x in an unsorted

Question

Given below is a randomized algorithm for searching for a value x in an unsorted array consisting of n elements. The strategy it utilizes is as follows. It randomly picks an index i between 1 and n (inclusive). If A[i] = x, it terminates. Otherwise, it continues picking random indices until it finds an index j such that A[j] = x, or it has checked every element of A. Note that it may examine a given element more than once. Give the average-case running time both in terms of T(n) and O() for this algorithm. Clearly explain how you arrived at your answer. Assume we are using 1-based indexing for the array.

Hint: Look up information about simple probability experiments, maybe a particular kind of distribution that begins with a ‘B’

search(x, A):

n = A.length();

checked = { };

found = false;

while ((! found) && (checked.size() != n)) do // assume checked.size() takes O(1) time

{

i = RANDOM(1, n); if (A[i] == x) found = true; else checked = checked U i; // assume this can be done in O(1) time

}

return(found);

Explanation / Answer

If you're doing a linear search through the array, then the average time complexity of finding one of M elements in an array with N elements will be O(P) where P is the average index of the first of the sought elements.

let's take an example of array 1 , 2 , 3 , 4 , 5

to search element 4 the complexity is O(4) searching from start using linear search .

to search element 4 the complexity is O(2) searching from end using linear search.

But here the thing is that to search the element index of the array is randomy generated between 1 to n .

Otherwise check for another generated index j and search froward until the whole list is visited .

let's talk about best case -

suppose it was generated in the first random index of i then complexity = O(1) .

let's talk about worst case -

while ((! found) && (checked.size() != n)) do //while loop is taking O(n) until the size becomes n

{

i = RANDOM(1, n); if (A[i] == x) found = true;//won't be executed till n-1 but this step takes O(1) time

else

{

checked = checked U i; // assume this can be done in O(1) time

}

}

so complexity is O(n).

average case -

we are picking the index randomly so we don't know where can we find our element to be searched in the list so complexity of average case can't be determined anyhow.

So complexity of the worst case depends on the manner of generation of random values as index.

but it's compulsory that the complexity of average case exists between O(1) to O(n);

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.