1. What will be the output of the following pseudocode for p = 3 and q = 4?
int fun1(int p, int q)
if(q EQUALS 0)
return 0
if(q mod 2 EQUALS 0)
return fun1(p + p, q/2) .
return fun1(p + p, q/2) + p
End function fun1()
A. None of the options
B. 7
C. 12
D. 8
EXPLANATION
Answer : Option C
Explanation:
Here initially p =3, q=4. In this question we are using recursive function.
If ( 4 == 0 ) is false so it will go to next if condition
If ( 4 % 2 == 0 ) -> if(true) so, here it will return fun1(p + p, q/2 )
That is fun1(6,2) now the new value of p=6 and q=2
Again same if condition will work as earlier
If(2 % 2 == 0) ->of (true) so here it will return fun1(6 + 6 , 2/2)
That is fun1(12,1) again p=1, q=1.
This time both if condition will return false so it will go to the last return statement.
That is
Return fun1(p+p, q/2) + p
Fun1(12+12, 1/2) + 12 ->fun(24,0) + 12
This time q is 0. So, if(q==0) will return 0. That means fun1(24,0) this function will return 0
So finally 0 + 12 = 12
Answer is option c
2. What is the time, and space complexity of the following code:
int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
- O(N * M) time, O(1) space
- O(N + M) time, O(N + M) space
- O(N + M) time, O(1) space
- O(N * M) time, O(N + M) space
EXPLANATION
O(N + M) time, O(1) space
Explanation: The first loop is O(N) and the second loop is O(M). Since N and M are independent variables, so we can’t say which one is the leading term. Therefore Time complexity of the given problem will be O(N+M). Since variables size does not depend on the size of the input, therefore Space Complexity will be constant or O(1
3. What is the time complexity of the following code:
int a = 0;
for (i = 0; i < N; i++) {
for (j = N; j > i; j–) {
a = a + i + j;
}
}
- O(N)
- O(N*log(N))
- O(N * Sqrt(N))
- O(N*N)
EXPLANATION
Answer 4. O(N*N)
Explanation: The above code runs total no of times
= N + (N – 1) + (N – 2) + … 1 + 0
= N * (N + 1) / 2 = 1/2 * N^2 + 1/2 * N
O(N^2) times.
4. What is the time complexity of the following code:
int i, j, k = 0;
for (i = n / 2; i <= n; i++) {
for (j = 2; j <= n; j = j * 2) {
k = k + n / 2;
}
}
- O(n)
- O(N log N)
- O(n^2)
- O(n^2Logn)
EXPLANATION
O(nLogn)
Explanation: The above code runs total no of times
= N + (N – 1) + (N – 2) + … 1 + 0
= N * (N + 1) / 2 = 1/2 * N^2 + 1/2 * N
O(N^2) times.
5. What is the time complexity of the following code:
int i, j, k = 0;
for (i = n / 2; i <= n; i++) {
for (j = 2; j <= n; j = j * 2) {
k = k + n / 2;
}
}
- O(n)
- O(N log N)
- O(n^2)
- O(n^2Logn)
EXPLANATION
O(nLogn)
Explanation: If you notice, j keeps doubling till it is less than or equal to n. Several times, we can double a number till it is less than n would be log(n). Let’s take the examples here. for n = 16, j = 2, 4, 8, 16 for n = 32, j = 2, 4, 8, 16, 32 So, j would run for O(log n) steps. i runs for n/2 steps. So, total steps = O(n/ 2 * log (n)) = O(n*logn).
6. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?
- X will always be a better choice for small inputs
- X will always be a better choice for large inputs
- Y will always be a better choice for small inputs
- X will always be a better choice for all inputs
EXPLANATION
X will always be a better choice for large inputs
Explanation: In asymptotic analysis, we consider the growth of the algorithm in terms of input size. An algorithm X is said to be asymptotically better than Y if X takes smaller time than y for all input sizes n larger than a value n0 where n0 > 0.
7. What is the time complexity of the following code:
int a = 0, i = N;
while (i > 0) {
a += i;
i /= 2;
}
- O(N)
- O(Sqrt(N))
- O(N / 2)
- O(log N)
EXPLANATION
O(log N)
Explanation: We have to find the smallest x such that ‘(N / 2^x )< 1 OR 2^x > N’ x = log(N).
8. What will be the time complexity of the following code?
for(var i=0;i<n;i++)
i*=k
- O(n)
- O(k)
- O(logkn)
- O(lognk)
EXPLANATION
O(logkn)
Explanation: Because the loop will run kc-1 times, where c is the number of times i can be multiplied by k before i reaches n. Hence, kc-1=n. Now to find the value of c we can apply log and it becomes logkn.
9. What will be the time complexity of the following code?
int value = 0;
for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
value += 1;
- n
- (n+1)
- n(n-1)
- n(n+1)
EXPLANATION
n(n-1)
Explanation: First for loop will run for (n) times and another for loop will be run for (n-1) times as the inner loop will only run till the range i which is 1 less than n , so overall time will be n(n-1).
10. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?
- X will always be a better choice for small inputs
- X will always be a better choice for large inputs
- Y will always be a better choice for small inputs
- X will always be a better choice for all inputs
EXPLANATION
X will always be a better choice for large inputs
Explanation: In asymptotic analysis, we consider the growth of the algorithm in terms of input size. An algorithm X is said to be asymptotically better than Y if X takes smaller time than y for all input sizes n larger than a value n0 where n0 > 0.
Leave a Reply