Q1- What is the time complexity of the recurrence equation T(n) = 4T(n/2) + n2?
(a) θ(n2)
(b) θ(n3)
(c) θ(nlogn)
(d) θ(n2logn)
(d)
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.
Q2- Which of the following is true
- (½)n = small-omega(n)
- (½)n = Big-Omega(n2)
(a) 1 is correct
(b) 2 is correct
(c) Both are correct
(d) None is correct
(d)
Q3- Which of the following is true
- (½)n2 = small-oh(n2)
- (½)n = Theta(n)
(a) 1 is correct
(b) 2 is correct
(c) Both are correct
(d) None is correct
(b)
Q4 – Exact Time Complexity of T(n) = 3n3 + 5n2 + 24
(a) Theta(n3)
(b) Theta(n5)
(c) Big-Oh(n3)
(d) Big-Omega(n3)
(a)
Theta notation means tightly bound. So, whenever exact word comes in the question, choose theta complexity.
Q5- f(n) = Big-Omega(g(n)) if and only if
(a) g(n) = small-oh(f(n))
(b) g(n) = small-omega(f(n))
(c) g(n) = Big-omega(f(n))
(d) g(n) = Big-Oh(f(n))
(d)