For the following snippets of code, compute the running time function T(n) by determining the number of times each line executes. In each case determine the best case and the worse case running time.

(a) Algorithm 1: //Input: A nonnegative integer n

S = 0

for i = 1 to n do

S = S + i * i return S

(b) Algorithm 2:

//Input: An array A[0..n-1] of n real numbers

minval = A[0]

maximal = A[0]

for i = 1 to n-1 do

if A[i] < minval

minval = A[i]

if A[i] > maxval

maxval = A[i]

return maxval - minval

(c) Algorithm 3:

//Input: A matrix A[0..n-1, 0..n-1] of real numbers

for i = 0 to n-1 do

for j = i+1 to n-1 do

if A[i, j] A[j, i]

return false

return true