Consider the following pseudocode: Algorithm moveDown (a) a is an array of numbe
ID: 3856234 • Letter: C
Question
Consider the following pseudocode:
Algorithm moveDown (a) a is an array of numbers
int i =1 n = a. length
while (a[i] > a[2"i] II > a[2"i+1]) && 2'i+1 < n
if a[2'il >= a(2'i +1] largest = 2"i
else largest = 2"i + 1
temp = a[i]
a[i] = a[largest]
a[largest] = temp
i = largest
(a) (2 points) Determine the exact number of statements (i.e. use the statement counting approach)
that are executed during one iteration of the while loop in the worst case.
Your answer should be expressed in terms of fl (the length of the array) Show all calculations.
(b) (5 points) Determine the exact number of times the while loop executes in the worst case.
(c) (3 points) Determine the exact number of statements executed in the worst case by the whole algorithm.
(d) (1 point) Identify an Active Operation
(e) (2 points) Determine the exact number of times the active operation is executed.
(f) (2 points) Express the answers to parts c) and e) in big-0 notation.
Explanation / Answer
(a)
Assuming that in the worst case, the statement a[2'i] >= a(2'i +1]) is not true.
Then, for one iteration of while loop, the step count is as follows:
Count Algorithm Step
1 int i =1
1 n = a. length
1 while (a[i] > a[2"i] || > a[2"i+1]) && (2'i+1 < n)
1 if (a[2'i] >= a(2'i +1])
0 largest = 2"i
1 else largest = 2"i + 1
1 temp = a[i]
1 a[i] = a[largest]
1 a[largest] = temp
1 i = largest
The total count of statements that are executed outside the while loop in the worst case are 2.
The total count of the statement of while loop is 1 for one iteration.
The total count of statements that are executed inside the while loop in the worst case during a single iteration are 6.
Hence, the total count of statements that are executed in the worst case are 9.
(b)
The while loop runs till the conditions (a[i] > a[2"i] || > a[2"i+1]) && (2'i+1 < n) are true.
In the worst case, we assume that the condition (a[i] > a[2"i] || > a[2"i+1]) is always true and the loop run for the maximum possible times.
The variable n is the length of the array. Thus, the loop runs till (2'i+1 < n) is true.
The value of the variable i is changed in the loop by the variable largest.
In the worst case the variable i will go upto the last value of the array and the value of n will be a power of 2.
Also, for the worst-case execution, consider that the condition (a[2'i] >= a(2'i +1]) is always true so that the value of i changes to 2"i rather than to 2"i+1.
The loop starts with the value of the variable i as 1.
For i=1, (After 0 execution i=20)
Value of the variable largest changes to 2"i that is 2.
Now i=largest, thus, the value of i is now 2.
For i=2, (After 1 execution i=21)
Value of the variable largest changes to 2"i that is 4.
Now i=largest, thus, the value of i is now 4.
For i=4, (After 2 executions i=22)
Value of the variable largest changes to 2"i that is 8.
Now i=largest, thus, the value of i is now 8.
For i=8, (After 3 executions i=23)
Value of the variable largest changes to 2"i that is 16.
Now i=largest, thus, the value of i is now 10.
For i=16, (After 4 executions i=24)
Value of the variable largest changes to 2"i that is 32.
Now i=largest, thus, the value of i is now 2.
For i=n, the loop will not run. (After p executions i=2p)
Assume that the loop executed for p times.
Then, n=2^p.
Now,
2p = n
p = log2 n
Thus, the loop will execute for log2 n times.
(c)
In the worst case, the statements inside the while loop will execute for log2 n times.
The statement containing the while conditions will run for log2 n+ 1 times.
The statements outside the while loop are executed exactly 1 times.
Number of statements that are executed inside the while loop are 6.
Number of statements outside the while loop are 2.
Total count of the statements executed is as follows:
2 + 6log2 n + (1) = 6log2 n +3
Thus, the exact number of statements that are executed is 6log2 n +3.
(d)
The operation which is done frequently again and again in a program is known as an active operation.
For the given algorithm, the loop statement as well all the statements inside the loop are active operations.
One of the active operations for the given algorithm is as follows:
a[i] = a[largest]
(e)
The active operation a[i] = a[largest] is executed 6 times.
(f)
For (c) part, the exact number of statements that are executed is 6 +3
6log2 n +3 is in the of order log2 n. Thus, the answer in Big-O notation is as follows:
O(log2 n).
For (e) part, the active operation is performed 6log2 n times 6log2 n is in the of order log2 n. Thus, the answer in Big-O notation is as follows:
O(log2 n).