retagged by
429 views
1 votes
1 votes
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
retagged by

1 Answer

Related questions

0 votes
0 votes
1 answer
1
Shreya2002 asked Oct 27, 2022
1,030 views
How to solve this recurrence relationT(n)= T(0.09n) + T(0.91n) + cnwhere c is constant and T(1)=1options are-
1 votes
1 votes
2 answers
2
srestha asked May 10, 2019
844 views
What is the solution of recurrence relation$T\left ( n \right )=T\left ( n-1 \right )+n$
2 votes
2 votes
2 answers
3
pradeepchaudhary asked Jul 14, 2018
9,130 views
Q.6 The time complexity of an algorithm T(n), where n is the input size, is given by— T(n)= T(n-1) + 1/n, if n>1 = 1, otherwise.The order of the algorithm is�...
1 votes
1 votes
2 answers
4