$1.$ Master$$s theorem is used for?

$*$

$1$ point

solving recurrences

calculating the time complexity of any code

analysing loops

solving iterative relations

$2.$ How many cases are there under Master$$s theorem?$*$

$1$ point

$4$

$3$

$2$

$6$

$3.$ What is the value of following recurrence.

T$($n$)=$ T$($n$/4)+$ T$($n$/2)+$ cn$2$

T$(1)=$ c$$

T$(0)=0$

Where c is a positive constant

$*$

$1$ point

O$($n$2)$

O$($n$3)$

O$($nLogn$)$

O$($n$2$ Logn$)$

$4.$ What is the time complexity of the following recursive function:$$

$$int DoSomething $($int n$)$

$\{$

$$ if $($n $<=2)$

$$ return $1$;

$$ else $$

$$ return $($DoSomething $($floor$($sqrt$($n$)))+$ n$)$;

$\}$

$($A$)$theta$($n$)$

$($B$)$theta$($nlogn$)$

$($C$)$theta$($logn$)$

$($D$)$theta$($loglogn$)$

$*$

$1$ point

$($A$)$

$($B$)$

$($C$)$

$($D$)$

$5.$ The time complexity of the following C function is $($assume n $>0)$

int recursive $($mt n$)$

$\{$

$$if $($n $==1)$

$$return $(1)$;

$$else

$$return $($recursive $($n$-1)+$ recursive $($n$-1))$;

$\}$

$0($n$)$

$0($nlogn$)$

$0($n$^2)$

$0(2^$n$)$

$*$

$1$ point

$0($nlogn$)$

$0($n$^2)$

$0($n$)$

$0(2^$n$)$

$6.$ What is the asymptotic value for the recurrence equation$$T$($n$)=2$T$($n$/2)+$ n$?*$

$1$ point

O$($n log n$)$

O$($n$)$

O$($n$^2$ log n$)$

O$($n$^2)$

$7.$ The master theorem$*$

$1$ point

Cannot be used for divide and conquer algorithms

Assumes the subproblems are unequal sizes

Cannot be used for asymptotic complexity analysis

Can be used if the subproblems are of equal size

$8.$ Arrange the following recurrence relations in increasing order of their time capacity.$$

$($A$)$ T$($n$)-$ T$($n$/2)+1$

$($B$)$ T$($n$)=2$T$($n$/2)+$ n$$

$($C$)$ T$($n$)=3$T$($n$/3)+$ n$$

$($D$)$ T$($n$)=2$T$($n$/2)+$n$$

$($E$)$ T$($n$)=$T$($n $-1)+1$

Choose the correct answer from the options given below:$$

$1.($E$),($A$),($B$),($D$),($C$)$

$2.($A$),($E$),($D$),($B$),($C$)$

$3.($E$),($A$),($D$),($B$),($C$)$

$4.($A$),($B$),($D$),($E$),($C$)$

$*$

$1$ point

Option $1$

Option $4$

Option $2$

Option $3$

$9.$ Under what case of Master$$s theorem will the recurrence relation of binary search fall?

$*$

$1$ point

$2$

$3$

It cannot be solved using master$$s theorem

$1$

$10.$ What is the result of the recurrences which fall under second case of Master$$s theorem $($let the recurrence be given by T$($n$)=$aT$($n$/$b$)+$f$($n$)$ and f$($n$)=$n$^$c$?$

$*$

$1$ point

T$($n$)=$ O$($n$^2)$

T$($n$)=$ O$($n$^$c log n$)$

T$($n$)=$ O$($f$($n$))$

T$($n$)=$ O$($nlogba$)$

$11.$Predict output of following program$$

#include

int fun$($int n$)$

$\{$

$$ if $($n $==4)$

$$return n;

$$ else return $2*$fun$($n$+1)$;

$\}$

int main$()$

$\{$

$$printf$("\%$d$",$ fun$(2))$;

$$return $0$;

$\}$

$*$

$1$ point

$4$

$16$

$8$

Runtime Error

$12.$Recursion is a process in which a function calls$*$

$1$ point

None of these

itself

another function

main$()$ function

$13.$ Which of the following problems can$$t be solved using recursion?

$*$

$1$ point

Factorial of a number

Problems without base case

Nth fibonacci number

Length of a string