EXERCISE

8.1.2: Arithmetic and geometric sequences.

Give the first six terms of the following sequences. You can assume that the sequences start with an index of 1.

1) A geometric sequence in which the first value is 27 and the common ratio is 1/3.

2) CountValuesLessThanT Input: a1, a2,...,an n, the length of the sequence. T, a target value. Output: The number of values in the sequence that are less than T. count = 0 For i = 1 to n If ( ai < T ), count := count + 1 End-for Return( count )

(a)

Characterize the asymptotic growth of the worst-case time complexity of the algorithm. Justify your answer.

3. MaximumSubsequenceSum Input: a1, a2,...,an n, the length of the sequence. Output: The value of the maximum subsequence sum. maxSum := 0 For i = 1 to n thisSum := 0 For j = i to n thisSum := thisSum + aj If ( thisSum > maxSum ), maxSum := thisSum End-for End-for Return( maxSum )

(a)

Characterize the asymptotic growth of the worst-case time complexity of the algorithm. Justify your answer.

(b)

Can you find an algorithm that solves the same problem whose worst-case time complexity is linear?