1       //pre:  (n  is  an  integer) ∧ (n  >=  1)

2       sum ← 0

3       j ← 1

4      m ← 2*n

1

1

3

5      while  (j  <= m) 3

6              k ← 1                                                   1

7              while  (k  <= j) 3

8                     prod ← j*k                                  4

9                      sum ← sum  + prod                       4

10                    k ← k+1                                        3

11            j ← j+1                                               3

Now we need to analyze the loops.

(1) Let j ≤ 2n be fixed, and consider the inner loop in lines 7 - 10.

❼ From line 6, k starts at 1. From line 10, k counts up by 1’s.

❼ The loop condition evaluates to true for k = 1, 2,...,j. For each such k, the number of

primitive operations due to lines 7 - 10 is

3 + 4 + 4 + 3 = 14.

The total number of primitive operations due to the iterations of the loop is

j

X(14) = 14j

k=1

❼ When k = j + 1, the loop condition in line 7 is checked for a final time and evaluates to

false.  This contributes another 3 primitive operations.  Thus the total due to the loop in lines 7 - 10 is

14j + 3.

(2) Now consider the outer loop in lines 5 - 11.

❼ From line 3, j starts at 1. From line 11, j counts up by 1’s. Also note that from line 4,

m = 2n.

❼ The loop condition evaluates to true for j = 1, 2,...,m: that is, for j = 1, 2,..., 2n. For

each such j, lines 5, 6, 11, and the inner loop in lines 7 - 10 are all executed. Using the line-by-line counts and the result from (1), the number of primitive operations in one iteration is

3 + 1 + (14j + 3) + 3 = 14j + 10.

The total number of primitive operations due to the iterations of the outer loop is

2n

X(14j + 10)

j=1

2n                    2n

=   X(14j) + X(10)

j=1                 j=1

=   14 + 10(2n)

=   14n(2n + 1) + 20n

❼ When j = 2n+1, the loop condition in line 5 is checked for the final time and evaluates to

false. This contributes another 3 operations. The total number of primitive operations due to lines 5 – 11 is

14n(2n + 1) + 20n + 3.

Optional: this simplifies to 28n2 + 34n + 3.

(3) When the program runs, lines 2, 3 and 4 are all executed once, followed by the loop in lines

5 – 11.  Using the result from (2) and the line-by-line counts, the total number of primitive operations as a function of n is

f(n) = 1 + 1 + 3 + [14n(2n + 1) + 20n + 3] = 14n(2n + 1) + 20n + 8.

Optional: this simplifies to

f(n) = 28n2 + 34n + 8.

2. Parts (a) and (b) below refer to the following code.  Assume that A is an integer array of length n, where n ≥ 1.

1       //pre:   A.length  >=  1

2      n ← A.length

3       j ← 0

4      while  (j  < n)

5              if  (A[j]  < 0)

6                     k ← j+1

7                     while  (k  < n)

8                             A[k] ← A[k]  + n

9                             k ← k+1

10            j ← j+2

(a)  [9 marks] Find f(n), the number of steps that the following program executes as a

function of the array length n, in the worst case.  Use the definition of a step discussed in pages 8–10 of CostFunctions  1 and used throughout the Week 4 content.  You can assume that A.length is a primitive operation. Show your work, and simplify your final answer until no summation notation appears.

You will have to consider separately the case where n is even and the case where n is odd. Write your answer as a piecewise-defined function of n:

f1(n),   n even

f2(n),   n odd

Solution

(1) Observe that each line individually contributes 1 step.

(2) The worst case occurs when the if condition in line 5 evaluates to true every time it is checked. Assume that A[j] is negative every time line 5 is reached.

(3) Let j < n be fixed, and consider the inner loop in lines 7 - 9.

❼ From line 6, k starts at j + 1. From line 9, k counts up by 1’s.

❼ The values of k for which the loop condition is true are k = j + 1,j + 2,...,n − 1.

For each such k, lines 7, 8 and 9 are all executed, for a total of 3 steps.  The total number of steps due to the iteration of the inner loop is

n − 1

X  (3) = 3(n − j − 1).

k=j+1

❼ When k = n, the loop condition is checked for a final time and evaluates to false.

This contributes 1 additional step. The total number of steps due to lines 7 - 9 is 3(n − j − 1) + 1 = 3n − 3j − 2.

(4) Now consider the outer loop in lines 4 - 10.

❼ From line 3, j starts at 0.  From line 10, j counts up by 2’s.  Therefore j is always

even.

❼ Let m = . Then m starts at 0 and counts up by 1’s.

❼ The loop condition in line 4 evaluates to true as long as j < n, or in other words, as long as m < .

(5) Either n is even or n is odd. Proceed by cases.

(6) Case 1. Suppose that n is even.

❼ The loop condition in line 4 evaluates to true when j = 0, 2, 4,...,n − 2.  That is, when m = 0, 1, 2,..., − 1.  For each such m, by the assumption from (2), lines 4, 5, 6, 10, and the inner loop in lines 7 - 9 are all executed. Using the result from (3), the number of steps due to one iteration of the loop is

1 + 1 + 1 + (3n − 3j − 2) + 1 = 3n − 3j + 2,

which we rewrite in terms of m as

3n − 6m + 2.

The total number of steps due to iterations of the loop is

n/2 − 1

(3n − 6m + 2) m=0

n/2 − 1                           n/2 − 1

=    X (3n + 2) − 6  X  m

m=0                             m=0

= (3n + 2) − 3 − 1

❼ When j = n, the loop condition in line 4 is checked for the final time and evaluates

to false, contributing one more step. The total number of steps due to lines 4 – 10 is

(3n + 2) − 3 − 1 + 1.

Optional: this simplifies to

3n2 5n

4        2

(7) Case 2. Suppose that n is odd.

❼ Now the loop condition in line 4 evaluates to true when j = 0, 2, 4,...,n − 1. That is, when m = 0, 1, 2,..., . As in Case 1, the number of steps due to one iteration of the loop is

3n − 6m + 2.

The total number of steps due to iterations of the loop is

(n − 1)/2                                           (n − 1)/2                           (n − 1)/2

X                                    X                        X

m=0                                                 m=0                                m=0

= (3n + 2) − 3

❼ When j = n+1, the loop condition in line 4 is checked for the final time and evaluates

to false, contributing one more step. The total number of steps due to lines 4 – 10 is

(3n + 2) − 3 + 1.

Optional: this simplifies to

3n2 5n     11

4        2       4

(8) In all cases, when the program runs, lines 2, 3 and the loop in lines 4 - 10 are all executed. Lines 2 and 3 contribute an additional 2 steps to the results from (6) and (7). Thus the number of steps as a function of n, in the worst case, is

f(n) =

+ + 3,     n even

4   +  2  +  4 ,   n odd

(b)  [2 marks] Consider the specific instance where n = 7.  Give an example of an array A

of length 7 such that the worst case number of steps will occur if A is the input to this code. Briefly (1-3 sentences) justify why the worst case will occur when your example is used as the input.

Solution

Here is an array of length 7 for which the worst case will occur:

A  =  {-50,-50,-50,-50,-50,-50,-50}.

Notice that the inner loop in lines 7 - 9 adds n to each entry in A that comes after the current entry A[j]. In this case, n = 7, and the inner loop is executed at most = 3 times, so at most 7 × 3 = 21 will be added to each entry in A. Since all entries in A begin at −50, the result will still be negative and the if condition in line 5 will always evaluate to true.

6

3. Parts (a) and (b) below refer to the following code.  Assume that A is an array of integers whose length n is even and at least 2.

In this question, you will count array accesses, not steps. An array access is any instance in which a value A[k] is used in a calculation or comparison, or any instance in which a new value is assigned to A[k].  Do not count the operation A.length, since this command does not use a particular entry in A.

1       //pre:  (A.length  >=  2) ∧ (A.length  is  even)

2      n ← A.length

3       if  (A[0]  < A[n-1])

4              i ← 0

5              while  (i  < n/2)

6                     tmp ← A[i]

7                     A[i] ← A[n-1-i]

8                     A[n-1-i] ← tmp

9                      i ← i+1

10     sum ← 0

11     j ← 0

12     while  (j  < n)

13            if  (A[j] %  2  ==  0)

14                    sum ← sum  + A[j]

15            else

16                    k ← j

17                    while  (k  < n)

18                           sum ← sum  + A[k]

19                           k ← k+1

20            j ← j+1

(a)  [8 marks] Find f(n), the number of array accesses performed in this code as a function of

the array length n, in the worst case. Make sure you are counting array accesses and not steps. Show your work, and simplify your answer until no summation notation appears.

Solution

(1) Here are the counts of array accesses per line:

1       //pre:  (A.length  >=  2) ∧ (A.length  is  even)

2      n ← A.length                                                            0

3       if  (A[0]  < A[n-1]) 2

4              i ← 0                                                                  0

5              while  (i  < n/2) 0

6                     tmp ← A[i]                                                 1

7                     A[i] ← A[n-1-i]                                        2

8                     A[n-1-i] ← tmp                                          1

9                      i ← i+1                                                       0

10     sum ← 0                                                                      0

11     j ← 0                                                                          0

12     while  (j  < n) 0

13            if  (A[j] %  2  ==  0)                                          1

14                    sum ← sum  + A[j]                                      1

15            else

16                    k ← j                                                           0

17                    while  (k  < n) 0

18                           sum ← sum  + A[k]                               1

19                           k ← k+1                                               0

20            j ← j+1                                                              0

(2) There is an if-block in lines 3 - 9. The check of the if condition in line 3 contributes

2 array accesses. For the worst case to occur, this if condition must evaluate to true.

(3) Assume that A[0]  < A[n-1], so that the code in lines 4 - 9 is executed.

(4) Consider the while loop in lines 5 - 9.

❼ From line 4, i starts at 0. From line 9, i counts up by 1’s.

❼ The loop condition in line 5 evaluates to true when i = 0, 1,..., − 1. For each such

i, using the table shown in (1), the number of array accesses due to one iteration

of the loop is 1 + 2 + 1 iterations of this loop is

= 4.  Therefore the total number of array accesses due to

n/2 − 1

X (4) = 2n.

i=0