Name:

Quiz: Running-Time Analysis

Prof. Szenher

CSCI 235, Spring 2003

1. What is the worst-case running time, in big-O notation, of each of the following tasks (you need not show your work):

a) (8%) Summing all n integers in an array of n elements. à O(n)

b) (8%) Printing every other element in an array of n elements. à O(n)

c) (8%) Displaying the last element in an array with n elements.àO(1)

d) (8%) Displaying the last element in a linked list with n nodes. àO(n)

e) (8%) Displaying the middle element in a linked list with n nodes. àO(n)

2. This question concerns the following algorithm:

//precondition: A[] is an array of n integers

int f (int A[], int n,) {

int c = sqrt (A[0] * A[0]); ß1

for (int j = 1; j < n; j++) { ßn

if ((A[j] > c) || (A[j] < -c)){ ßn

c = sqrt (A[j] * A[j]); ßn

}

}

return c; ß1

}

a) (10%) Describe, in one or two sentences, the purpose of this algorithm.

b) (15%) Describe the worst-case input to this algorithm.

c) (35%) Give the exact worst-case running time of this algorithm

a) This algorithm finds the largest absolute value in an unsorted array of integers.

b) array of integers sorted in ascending order

c) = 3n+2