== 1 ==
Consider the following procedure for multiplying two numbers:
MULT(n1,n2) COST TIMES
answer = n1 c1 1
for i = 1 to n2 c2 n2 + 1 (the for-loop test is executed 1 more time)
answer = answer + n1 c3 n2
Compute the running time for MULT.
T(n) = (c1 * 1) + (c2 * (n2 + 1)) + (c3 * n2)
= (c2 + c3)*n2 + c1 + c2
Why is it not relevant to speak about best vs worst case for MULT?
MULT solely depends on the size of n2.
There are no conditionals (in if-then-else, while, etc), therefore the actual values of n1 and n2 do not influence whether some instructions are executed fewer times.
== 2 ==
Compute the worst-case running time of INSERTION-SORT, and simplify the expression you obtain as much as possible.
(Solved in class, see the lecture recording)
== 3 ==
Compute the average-case running time of INSERTION-SORT, and simplify the expression you obtain as much as possible.
The average case is when t_j = j/2. Then we have,
T(n) = c1*n + c2*(n-1) + c4*(n-1)
+ c5 * SUM (from j = 2 to n): j/2
+ c6 * SUM (from j = 2 to n): (j/2 -1)
+ c7 * SUM (from j = 2 to n): (j/2 -1)
+ c8*(n-1)
We have that:
SUM (from j = 2 to n): j/2 = (SUM (from j = 1 to n): j/2) - 1
SUM (from j = 1 to n): j/2 = (SUM (from j = 1 to n)) / 2
SUM (from j = 1 to n) = n*(n+1) / 2
We also have
SUM (from j = 2 to n): (j/2 -1) = (SUM (from j = 1 to n): j/2) - (j/2-1 when j = 1) = (SUM (from j = 1 to n): j/2) + 0.5
Therefore: SUM (from j = 2 to n): j/2 = (n*(n+1) / 4) - 1 and the term with c5 is
c5 * SUM (from j = 2 to n): j/2 = c5 * ((n*(n+1) / 4) - 1) = (c5*n^2 + c5*n) / 4 - c5 = (c5/4)*n^2 + (c5/4)*n - c5
We also have
SUM (from j = 2 to n): (j/2 -1) = (SUM (from j = 1 to n): j/2) - (j/2-1 when j = 1) = (SUM (from j = 1 to n): j/2) + 1/2
Therefore: SUM (from j = 2 to n): (j/2 -1) = (n*(n+1) / 4) - 1 + 0.5 = (n*(n+1) / 4) - 1/2 and the term with c6 is
c6 * SUM (from j = 2 to n): (j/2 -1) = c6 * (n*(n+1) / 4) - 1/2 = (c6*n^2 + c6*n) / 4 - c6/2 = (c6/4)*n^2 + (c6/4)*n - c6/2
Similar for c7: (c7/4)*n^2 + (c7/4)*n - c7/2
All together:
T(n) = c1*n + c2*n-c2 + c4*n-c4
+ (c5/2)*n^2 + (c5/2)*n - c5
+ (c6/4)*n^2 + (c6/4)*n - c6/2
+ (c7/4)*n^2 + (c7/4)*n - c7/2
+ c8*n-c8
= (c5/2 + c6/4 + c7/4)*n^2 + (c1 + c2 + c4 + c5/2 + c6/4 + c7/4 + c8)*n - (c2 + c4 + c5 + c6/2 + c7/2 + c8)
== 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.
MATCH(A) COST TIMES
answer = "no" c1 1
for i = 1 to A.length c2 n+1
for j = 1 to A.length c3 n * (n+1)
if not(i == j) and A[i] == A[j] c4 n * n
answer = "yes" c5 SUM (from i = 1 to n, j = 1 to n): t(i,j) t(i,j) is 0 or 1 depending on whether not(i == j) and A[i] == A[j]
return answer c6 1
Compute the running time of MATCH.
T(n) = (c1 * 1) + (c2 * (n+1)) + (c3 * n * (n+1)) + (c4 * n * n) + (c5 * n * SUM (from j = 1 to n): t(i,j)) + (c6 * 1).
What is the best case? Compute the specific running time for the best case of MATCH.
The best case is when there are no repetition and the line answer = "yes" is never executed.
In that case: t(i,j) = 0 for all i,j, and we have
T(n) = (c1 * 1) + (c2 * (n+1)) + (c3 * n * (n+1)) + (c4 * n * n) + (c6 * 1).
= (c3 + c4)n^2 + (c2 + c3)n + c1 + c6
What is the worst case? Compute the specific running time for the worst case of MATCH.
The worst case is when all elements of the array are the same. Then answer = "yes" is executed every time.
In that case: t(i,j) = 1 for all i,j s.t. i is not j, and t(i,j) = 0 otherwise. Then we have
SUM (from j = 1 to n): t(i,j) = (SUM (from j = 1 to n): 1) - 1 (-1 because when i = j, t(i,j) = 0)
= n - 1
T(n) = (c1 * 1) + (c2 * (n+1)) + (c3 * n * (n+1)) + (c4 * n * n) + (c5 * n * (n-1)) + (c6 * 1).
= (c3 + c4 + c5)n^2 + (c2 + c3 - c5)n + c1 + c6