Algorithm Secret(A[0..n − 1]) //
Input: An array A[0..n − 1] of n real numbers
minval ← A[0];
maxval ←A[0]
for i ← 1 to n − 1 do
if A[i] < minval
minval ← A[i]
if A[i] > maxval
maxval ← A[i]
return maxval − minval
a. What does this algorithm compute?
b. What is its basic operation?
c. How many times is the basic operation executed?
d. What is the efficiency class of this algorithm?
Answers
Answer:
As the code states this algorithm will compute the difference between the maximum and the minimum value of the numbers inside an array
The basic operation here we are traversing the whole array and comparing the numbers with each other to find the max and min value among the numbers
This operation will be executed for n times where n is the number of items in the array.
Answer:
a. Largest and the smallest elements in the list.
b. Comparison
c. 2n times
d. O ( n)
Explanation:
a. Line 1, 2, and 3 are simple statements of declaration of varaibles and loop, but algorithm computation is the 'if' statements which are also the basic operations of the algorithm.
b. The basic operations can be addition/multiplication/division/comparison in an algorithm, so here we have two comparisons as basic operations of the algorithm.
c. The both comparison operations are independent and in each iteration they compare so basically the first operation "if A[i] < minval" will execute "n" times and the same for the second "if A[i] > maxval" will also execute "n" time so in total the basic operation executes n+n = 2n times.
d. The efficiency class of this algorithm is computed below:
minval ← A[0] => constant O(1)
maxval ←A[0] => constant O(1)
if A[i] < minval => constant O(n-1)
if A[i] > maxval => constant O(n-1)
return maxval − minval => constant O(1)
Total efficiency is 1 + 1 + (n-1) + (n-1) + 1 = 2n + 1 which can be reffered as O(n).