Question

Determine the running time of each of the algorithms below. For questions 2a. and 2b., you may determine the running time line-by-line (see Lecture 2, slide No. 8). For questions 2c – 2f, you may determine the running time by focusing on the basic operation of the algorithm.

a,sum = 0; for (i=1; i<=n; i++) sum += n;

b. Algorithm maxVal (numbers, n) currentVal ← numbers [0] for i ← 1 to n − 1 do if numbers [i] > currentVal then currentVal ←A[i] { increment counter i } return currentVal

c. Algorithm prefix1(X, n) //Input array X of n integers //Output array A of prefix averages of X A ← new array of n integers for i ← 0 to n − 1 do s ←X[0] for j ← 1 to i do s ←s + X[j] A[i] ←s / (i + 1) return A

d. Algorithm prefix2(X, n) //Input array X of n integers //Output array A of prefix averages of X A ← new array of n integers s ← 0 for i ← 0 to n − 1 do s ←s + X[i] A[i] ←s / (i + 1) return A

e. Algorithm SumTripleArray(X, n) //Input triple array X[][][] of n by n by n integers //Output sum of elements of X s ← 0 for i ← 0 to n − 1 do for j ← 0 to n − 1 do for k ← 0 to n − 1 do s ←s + X[i][j][k] return s

f. sum = 0; for( i = 0; i < n; i++) for( j = 0; j < n * n; j++) sum++;

Answer 1

a.

sum = 0;

for (i=1; i<=n; i++)

sum += n

the for loop runs for n time doing a constant operation each time so total running time is O(n)

b.

maxVal (numbers, n)

currentVal ← numbers [0]

for i ← 1 to n − 1

do if numbers [i] > currentVal

then currentVal ←A[i]

{ increment counter i }

return currentVal

the for loop runs for n-1 times doing at max 3 operation each time so total operation is <3n and runnning time =O(n)

c.

prefix1(X, n) //Input array X of n integers //Output array A of prefix averages of X

A ← new array of n integers

for i ← 0 to n − 1

do s ←X[0]

for j ← 1 to i do

s ←s + X[j]

A[i] ←s / (i + 1)

return A

The outer i loop runs for n times. and for each i value inner j loop runs for i times doing constant operations each time

so number of operations is c(1+2+3.......n-1) =O(n^2)

d.

prefix2(X, n) //Input array X of n integers //Output array A of prefix averages of X

A ← new array of n integers

s ← 0

for i ← 0 to n − 1 do

s←s + X[i]

A[i] ←s / (i + 1)

return A

there is only 1 i loop running n times, inside which a constant number of operations are being dome so running time is O(n)

e.

SumTripleArray(X, n) //Input triple array X[][][] of n by n by n integers //Output sum of elements of X

s ← 0

for i ← 0 to n − 1 do

for j ← 0 to n − 1 do

for k ← 0 to n − 1 do

s ←s + X[i][j][k] return

there are 3 nested loops i,j,k each running n times thus total running time is O(n^3)

f.

sum = 0;

for( i = 0; i < n; i++)

for( j = 0; j < n * n; j++)

sum++;

the outer i loop runs for n times and for each i value , the inner loop runs for n^2 times. so total running time is O(n^3)