== 1 ==
Consider the following procedure for multiplying two numbers:
MULT(n1,n2)
answer = n1
for i = 1 to n2
answer = answer + n1
Compute the running time for MULT.
Why is it not relevant to speak about best vs worst case for MULT?
== 2 ==
Compute the worst-case running time of INSERTION-SORT, and simplify the expression you obtain as much as possible.
(We will see this in the next lecture)
== 3 ==
Compute the average-case running time of INSERTION-SORT, and simplify the expression you obtain as much as possible.
== 4 ==
Provide the pseudo-code for a procedure called MATCH that takes an array and returns "yes" or "no" depending on whether the array contains duplicate elements.
The way MATCH works is by comparing each element with all the other elements of the array.
Compute the running time of MATCH.
What is the best case? Compute the specific running time for the best case of MATCH.
What is the worst case? Compute the specific running time for the worst case of MATCH.