46. Consider the following C function:

- Option : B
- Explanation :

Here foo(1) is recursive function. Spare complexity is O (n) as there can be at most O (n) active function at a time

You must be logged in to post a comment.

47. Consider the following C function:

- Option : B
- Explanation :

Space complexity is O (n). The space we need array of size O (n). The space required for recursive call would be O (1) as the value would be taken from array again & again

You must be logged in to post a comment.

You must be logged in to post a comment.

- Option : B
- Explanation :

T(n) = 2T(√n) + 1

Put n = 2^{k}

T(2^{k}) = 2T(n^{k/2}) + 1

replace T(2^{k}) by S(k)

S(k) = 2 S(k/2) + 1

Apply masters

K^{log22}⇒ k > 1

So Θ(k)

Now we know n = 2^{k}, k = log_{2}(n)

then Θ(logn)

You must be logged in to post a comment.

You must be logged in to post a comment.

- Option : D
- Explanation :

Since, j increases in power of 2's.

if statement j = j * 2 executes k times, then

2^{k}< n

⇒ k < log_{2}n

Since k will be integer,

total number of comparison

(when loop exits)

You must be logged in to post a comment.

You must be logged in to post a comment.

You must be logged in to post a comment.