Q9.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?
Answer : Option CExplaination / Solution:
The average case time can be lesser than or even equal to the worst case. So A(n) would be
upper bounded by W(n) and it will not be strict upper bound as it can even be same (e.g.
Bubble Sort and merge sort).
∴A(n) = O(W(n))
Q10. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem
with n discs is
Answer : Option DExplaination / Solution:
Let the three pegs be A,B and C, the goal is to move n pegs from A to C using peg B
The following sequence of steps are executed recursively
1.move n−1 discs from A to B. This leaves disc n alone on peg A --- T(n-1)
2.move disc n from A to C---------1
3.move n−1 discs from B to C so they sit on disc n----- T(n-1)
So, T(n) = 2T(n-1) +1
Total Question/Mark :
Scored Mark :
Mark for Correct Answer : 1
Mark for Wrong Answer : -0.5
Mark for Left Answer : 0