Q1- Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE? (GATE – 2012)
(A) A(n) = Omega(W(n))
(B) A(n) = Theta(W(n))
(C) A(n) = O(W(n))
(D) A(n) = o(W(n))
(c)
Always true is A(n) = O(W(n)).
Q2- What is the time complexity of the recurrence equation T(n) = 4T(n/2) + n2?
(a) θ(n2)
(b) θ(n3)
(c) θ(nlogn)
(d) θ(n2logn)
(a)
Applying master’s theorem,
Compiling time = n^log24 = n2
Running time = n2
Both are same so answer will be (running time)*logn which is equal to n2logn.
Q3- What is the time complexity of the recurrence equation T(n) = 2T(n/2) + n3?
(a) θ(n2)
(b) θ(n3)
(c) θ(nlogn)
(d) θ(n2logn)
(b)
Applying master’s theorem,
Compiling time = n^log22 = n
Running time = n3
Running time is bigger so answer is n3.
Q4- T(n) = T(n-1) + n – 1 is equal to
(a) O(logn)
(b) O(nlogn)
(c) O(n2)
(d) None
(c)
T(n) = T(n-1) + n – 1
T(n-1) = T(n-2) + n – 2
T(n-2) = T(n-3) + n – 3
…
T(2) = T(1) + 2
T(1) = 1 + x              x is constant and can be negative also
——————————-
T(n) = n-1 + n-2 + n-3 + … + 3 + 2 + 1 + x
T(n) = (n-1)(n-2)/2 + x
T(n) = O(n2)
Q5- What is the time complexity of the recurrence equation T(n) = 16T(n/4) + n2?
(a) θ(n2)
(b) θ(n3)
(c) θ(nlogn)
(d) θ(n2logn)
(d)
Applying master’s theorem,
Compiling time = n^log416 = n2
Running time = n2
Both are same so answer will be (running time)*log(n) which is equal to θ(n2logn).