Running time:

Let A be a two-dimensional array with n rows and n columns of numbers and

Incognito be an algorithm that outputs a certain number y defined as follows.

Incognito( A )

//input: a two-dimensional array A with n rows and n columns

// Output: a number

// Index of the array starts in [0][0]

1. n = A.rows()

2. y = 1

3. i = 0

4. while i < n do

5. x = A[i][0]

6. for j = 1 to n - 1 do

7. if A[i][j] > x

8. x = A[i][j]

9. y = y * x

10. i = i +1

11. return y

(a) Express the running time of Incognito( A ) as an explicit sum of the worst-case running times of each of the 11 steps.

(b) Find an explicit formula for your expression in part (a).

(c) Express your answer in part (b) using -notation.

(d) Briefly explain exactly what Incognito( A ) is computing.