**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