1. Consider the following algorithm: Algorithm Sum( m , n ) //Input: A positive
ID: 3671429 • Letter: 1
Question
1. Consider the following algorithm:
Algorithm Sum(m, n)
//Input: A positive integer n and another positive integer m n
//Output: ?
sum = 0
for i=m to n do
for j=1 to i do
sum = sum + 5
end for j
end for i
return sum
What does the algorithm compute? Show and determine the formula for the total number of additions (sum = sum + 5) performed by the algorithm.
_____________________________________________________________________________________________________
2. Consider the following recursive algorithm:
Algorithm Recursive(A[0..n-1])
//Input: A list A[0..n-1] of real numbers
//Output: ?
if n == 1 return A[0]
else do
value = Recursive(A[0..n-2])
if value > A[n-1] return value else return A[n-1]
end if
What does the algorithm compute? Establish and solve the recurrence relation for the total number of element comparisons (value > A[n-1]) performed by the algorithm.
Explanation / Answer
1.
This algorithm computes sum from m to n. suppose we consider n=7,m=5 then it returns 90.
Total number additions performed here in this case are 18 times
2.
This algorithm return the number of elements in the array i.e the lenght of array.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.