Discrete Mathematics for Computer Science

324 CHAPTER 5 Analysis of Algorithms

(b) Find the complexity of the following algorithm for computing the mean of n values:

INPUT: The number of values n and an array a[1.. n] containing them

OUTPUT: The mean of the values a[1], a[2]. a[n]

sumOfValues = 0

for i = 1 to n

sumOfValues = sumOfValues + a [i]

print sumOfValues/n

4. Find the complexity of the following algorithm for computing Fibonacci numbers:

INPUT: n E N

OUTPUT: F,

if n = 0 then

nthFib = I

else

if n = 1 then

nthFib = 1

else

fibnMinusTwo = 1

fibnMinusOne = 1

fori =2ton

nthFib = fibnMinusOne + fibnMinusTwo

fibnMinusTwo = fibnMinusOne

fibnMinusOne = nthFib

print nthFib