In computing the expectation, you had to consider a sample space and then look at the probabilities associated with each sample individually. In the analysis for $*$each$*$ sample, what were you trying to compute?

Group of answer choices

The number of times $`$max$`$ was updated

The minimum number of swaps needed to sort the input array

The number of possible inputs which require k assignments of $`$max$`$

The number of possible inputs where the array's maximum value is at index k

Flag question: Question $2$

Question $21$ pts

What is the average$-$case number of times that max is assigned a value by the algorithm FIND$-$MAX?

Group of answer choices

Theta$(1)$

Theta$($log n$)$

Theta$($n$)$

Theta$($n$^2)$

Something else

Flag question: Question $3$

Question $31$ pts

What is the worst$-$case number of times max is assigned a value by the algorithm FIND$-$MAX?

Group of answer choices

Theta$($log n$)$

Theta$($n$)$

Theta$($n$^2)$

Theta$($n$!)$