The Gateway to Computer Science Excellence
0 votes
28 views
RANDOMIZED-QUICKSORT(A, p, r)
1     if p < r
2     q = RANDOMIZED-PARTITION(A, p, r)
3     RANDOMIZED-QUICKSORT(A, p, q – 1)
4     RANDOMIZED-QUICKSORT(A, q + 1, r)


RANDOMIZED-PARTITION(A, p, r)
1     i = RANDOM(p, r)
2     exchange A[r] with A[i]
3     return PARTITION(A, p, r)

 

When RANDOMIZED-QUICKSORT runs, how many calls are made to the random number generator RANDOM in the worst case? How about in the best case? Give your answer in terms of  $\Theta$ notation.

in Algorithms by Boss (41.9k points) | 28 views

1 Answer

0 votes
In the worst case, RANDOM returns the index of the largest element each
time it’s called, so $\Theta (n)$ calls are made. In the best case, RANDOM returns
the index of the element in the middle of the array and the array has distinct
elements, so $\Theta (lg n)$ calls are made.
by Active (1.3k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,429 answers
195,206 comments
99,910 users