Algorithms
Q151.
The recurrence relation that arises in relation with the complexity of binary search is:Q152.
Let T(n) be defined by T(1)=10 and T(n+1)=2n+T(n) for all integers n \geq 1. Which of the following represents the order of growth of T(n) as a function of n?Q153.
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs isQ154.
When n=2^{2 k} for some k \geqslant 0, the recurrence relation T(n)=\sqrt{(} 2) T(n / 2)+\sqrt{n}, T(1)=1 evaluates to :Q155.
Let x_{n} denote the number of binary strings of length n that contain no consecutive 0s. The value of x_{5} isQ156.
The running time of an algorithm is represented by the following recurrence relation: T(n)=\left\{\begin{matrix} n & n\leq 3\\ T(\frac{n}{3})+cn& otherwise \end{matrix}\right. Which one of the following represents the time complexity of the algorithm?Q157.
Let x_{n} denote the number of binary strings of length n that contain no consecutive 0s. Which of the following recurrences does x_{n} satisfy?Q158.
Consider the following recurrence: T(n)=2T(\left \lceil \sqrt{n} \right \rceil)+ 1, T(1) = 1 Which one of the following is true?Q159.
Let T(n) be a function defined by the recurrence T(n) = 2T(n/2) + \sqrt n \text{ for }n \geq 2 and T(1) = 1 Which of the following statements is TRUE?