Q.1
Solve the following recurrence using Master’s theorem.
  • a) T(n) = O(n)
  • b) T(n) = O(log n)
  • c) T(n) = O(n2log n)
  • d) T(n) = O(n2)
Q.2
Solve the following recurrence using Master’s theorem.
  • a) T(n) = O(n2)
  • b) T(n) = O(n2 log n)
  • c) T(n) = O(2n)
  • d) cannot be solved
Q.3
Solve the following recurrence using Master’s theorem.
  • a) T(n) = O(n)
  • b) T(n) = O(log n)
  • c) T(n) = O(n2log n)
  • d) T(n) = O(n2)
Q.4
Solve the following recurrence using Master’s theorem.
  • a) T(n) = O(n)
  • b) T(n) = O(log n)
  • c) T(n) = O(n2log n)
  • d) cannot be solved using master’s theorem
Q.5
Solve the following recurrence using Master’s theorem.
  • a) T(n) = O(n)
  • b) T(n) = O(log n)
  • c) T(n) = O(n2log n)
  • d) cannot be solved using master’s theorem
Q.6
Solve the following recurrence using Master’s theorem.
  • a) T(n) = O(n!)
  • b) T(n) = O(n! log n)
  • c) T(n) = O(n2log n)
  • d) cannot be solved using master’s theorem
Q.7
Solve the following recurrence using Master’s theorem.
  • a) T(n) = O(n (log n)2)
  • b) T(n) = O(n log n)
  • c) T(n) = O(n2log n)
  • d) cannot be solved using master’s theorem
Q.8
What will be the recurrence relation of the following code? Int sum(int n) { If(n== return else return n+sum(n-1); }
  • a) T(n) = T(n/2) + n
  • b) T(n) = T(n-1) + n
  • c) T(n) = T(n-1) + O(1)
  • d) T(n) = T(n/2) + O(1)
Q.9
What will be the recurrence relation of the following code? int xpowy(int x, int n) if (n==returnif (n==return x; if ((n %==return xpowy(x*x, n/2); else return xpowy(x*x, n/* x;
  • a) T(n) = T(n/2) + n
  • b) T(n) = T(n-1) + n
  • c) T(n) = T(n-1) + O(1)
  • d) T(n) = T(n/2) + O(1)
Q.10
What will be the time complexity of the following code? int xpowy(int x, int n) { if (n== return if (n== return x; if ((n %== return xpowy(x*x, n/2); else return xpowy(x*x, n/* x; }
  • a) O(log n)
  • b) O(n)
  • c) O(n log n)
  • d) O(n2)
0 h : 0 m : 1 s