Description
Question 1. In pseudo code, describe Algorithm ComputeAverage(A,n) that returns, for an input of an array A with n elements, the average value of these n elements.
Question 2 & 3. Consider the following algorithm described in pseudo code.
Algorithm Compute(n)
Input: positive integer n
Output: sum of all integers from 1 to n
value ← 0
for i ← 0 to n1 do
value ← value + (i + 1)
end
return value

Determine the number of primitive operations of Algorithm Compute(n), counting assignments, comparisons, and returns only.

In pseudo code, describe Algorithm RecursiveCompute(n), an algorithm that outputs the sum of all integers from 1 to n as recursive algorithm.

Determine the number of primitive operations of Algorithm RecursiveCompute(n), counting assignments, comparisons, and returns only.

In pseudo code, describe Algorithm ComputeFast(n), an algorithm that outputs the sum of all integers from 1 to n in constant time.
Question 4. For the following, lg n = log2 n

Order the following functions by their growth rate (bigOh).
f ^{ }(n) = lg n 
f_{2}(n) = n^{3} + 882 

f 
(n) = 17n + 
n 

0 
1 



f_{4} (n) = n lg n^{3} 
f_{5}(n) = n^{3} lg n 
f_{6}(n) = 28n^{2} + 3 

Which of the following functions are bigtheta of one another?
g_{0} (n) = 17 · 2^{lg} ^{n} 
g_{1}(n) = 1032 
g_{2}(n) = n lg n 


1 
g_{5}(n) = 881n 
g_{6}(n) = n^{2} + 13 

g_{4}(n) = n 
+ 81 

2 
f_{3}(n) = 112 · 3^{n}
f_{7}(n) = 1^{n}
g_{3}(n) = n lg n + n
g_{7}(n) = 1^{n}
.
Question 5. Consider the following algorithm described in pseudo code.
. Algorithm arrayFind( , )
Input: An element and an element array
Output: The index such that = [ ] or −1 if no element of is equal to .
←0
while < do
if = [ ] then return
else ← +1
end
return −1
Counting assignments, comparisons, and returns only, calculate the worstcase, ( ), and bestcase, ( ), running times of Algorithm arrayFind.