327 views

1 Answer

0 votes
0 votes
We analyze the expected run time because it represents the more typical
time cost. Also, we are doing the expected run time over the possible random-
ness used during computation because it can’t be produced adversatively, unlike
when doing expected run time over all possible inputs to the algorithm.

Related questions

0 votes
0 votes
1 answer
2
akash.dinkar12 asked Jun 27, 2019
908 views
QUICKSORT(A,p,r) 1 if p < r 2 q = PARTITION(A,p,r) 3 QUICKSORT(A, p , q-1) 4 QUICKSORT(A, q + 1, r)How would you modify QUICKSORT to sort into nonincreasing order?
0 votes
0 votes
1 answer
3
akash.dinkar12 asked Jun 27, 2019
1,425 views
Give a brief argument that the running time of PARTITION on a subarray of size $n$ is $\Theta(n)$.
0 votes
0 votes
1 answer
4
akash.dinkar12 asked Jun 27, 2019
1,683 views
What value of $q$ does PARTITION return when all elements in the array $A[p..r]$ have the same value? Modify PARTITION so that $q=\lfloor(p+r)/2 \rfloor$ when all element...