1. Consider the following algorithm :
procedure Test(N)
/* N is positive integer power of 2 */
for i = 1 to N do
for j = 1 to i
Write i, j, N
endfor
endfor
If N > 1 then do
for i = 1 to 8 do
call Test (N/2)
endfor
enddo
end test
Let L(N) denote the number of lines written by Test (N). The recurrence relation
for L(N) is :
(A) L(N) = 8L(N) + N(N + 1)/2
(B) L(N) = 8L(N/2) + N(N – 1)/4
(C) L(N) = 4L(N/2) + N(N + 1)/2
(D) L(N) = 8L(N/2) + N(N + 1)/2
2. What is the complexity of the program in Q. No. 1 if the call to Test
(N/2) is removed from it ?
(A) O(N) (B) O(N2)
(C) O(1) (D) O(N3)
3. If N = 4 how many lines are printed by the program of Q. No. 1 ?
(A) 10 (B) 11
(C) 12 (D) 14
4. If N = 4, and the j-loop and the j variable in the write statement are removed
from Q. No. 1, what is the output of the program ?
(A) 1, 4, 2, 4, 3, 4, 4, 4 (B) 1, 2, 3, 4, 3, 4
(C) 1, 4, 2, 4, 5, 2, 1 (D) 1, 4, 2, 4, 3, 4, 4
5. If the if-statement in Q. No. 1 is removed, how many times is the recursive
call made ?
(A) 0 (B) 16
(C) 32 (D) 8