Q1- The running time of an algorithm T(n), where ‘n’ is the input size, is given by
T(n)=T(n-1) + 1/n, if n > 1
      1    , otherwise
The time complexity of the algorithm is
(a) n2
(b) n3
(c) log(n)
(d) n
(c)
T(n) = T(n-1) + 1/n
T(n-1) = T(n-2) + 1/(n-1)
T(n-2) = T(n-3) + 1/(n-2)
…
T(2) = T(1) + 1/2
T(1) = 1
———————
T(n) = 1 + 1/2 +1/3 +1/4 + … + 1/(n-1) + 1/n
This is a harmonic series and the series sum is log(n)
T(n) = O(log(n))
Q2- The running time of an algorithm T(n), where ‘n’ is the input size, is given by
T(n)= T(n-1) + T(n-2) – T(n-3), if n > 3
           n,       otherwise
The time complexity of the algorithm is
(a) n2
(b) n3
(c) log(n)
(d) n
(d)
T(1) = 1
T(2) = 2
T(3) = 3
T(4) = T(3) + T(2) – T(1) = 3 + 2 – 1 = 4
T(5) = T(4) + T(3) – T(2) = 4 + 3 – 2 = 5
So, we can say that T(n) = n
Q3- The order of an algorithm that finds whether a given Boolean function of ‘n’ variables, produces a 1 or not
(a) logarithmic
(b) linear
(c) exponential
(d) constant
(c)
Because you have to compute 2n times in the worst case of algorithm.
Q4- Which of the given options provides the increasing order of asymptotic complexity of function f1 = 2n, f2 = n3/2, f3 = n*log(n) and f4 = nlog(n)? (GATE – 2011)
(a) f3, f2, f4, f1
(b) f3, f4, f2, f1
(c) f2, f3, f4, f1
(d) f3, f2, f1, f4
(a)
Suppose n = 26 = 64
f1 = 2n = 264
f2 = n3/2 = 26*3/2 = 29
f3 = n*log(n) = 26*6 = 3*27
f4 = nlog(n) = 26*6 = 236
Q10- The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is (GATE – 2012)
(a) T(n) = 2T(n − 2) + 2
(b) T(n) = 2T(n − 1) + n
(c)Â T(n) = 2T(n/2) + 1
(d) T(n) = 2T(n − 1) + 1
(d)
If n = 1, then optimal execution time is 1.
If n = 2, then optimal execution time is 3.
If n = 3, then optimal execution time is 7.
If n = 4, then optimal execution time is 15.
Only (d) is confirming.