master-theorem

Consider the following recurrence relations: For all $n>1$, $$ \begin{aligned} & T_1(n)=4 T_1\left(\frac{n}{2}\right)+T_2(n) \\ & T_2(n)=5 T_2\left(\frac{n}{4}\right)+\theta\left(\...

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $\Theta(n)$ ?

For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers : $$T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)$$...

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? T(1) = 2T (n/2) + log n

The running time of an algorithm is represented by the following recurrence relation: $$T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$$ Wh...

Consider the following recurrence: $$T\left( n \right){\rm{ }} = {\rm{ 2T(}}\left\lceil {\sqrt n } \right\rceil {\rm{) + }}\,{\rm{1 T(1) = 1}}$$ Which one of the following is true?

Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 Which one of the following is FALSE?

If T 1 = O(1), give the correct matching for the following pairs: List - I (M) T n = T n - 1 + n (N) T n = T n/2 + n (O) T n = T n/2 + nlog n (P) T n = T n - 1 + log n List - II (U...

Let T(n) be the function defined by $$T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$$ Which of the following statements is true?

The recurrence relation $$\,\,\,\,\,$$ $$T\left( 1 \right) = 2$$ $$T\left( n \right) = 3T\left( {{n \over 4}} \right) + n$$ has the solution $$T(n)$$ equal to

The recurrence relation T(1) = 2 T(n) = 3T(n/4) + n has the solution, T(n) equals to

Solve the recurrence equations: $$\,\,\,\,\,\,\,\,\,\,T\left( n \right) = \left( {{n \over 2}} \right) + 1$$ $$\,\,\,\,\,\,\,\,\,\,\,T\left( 1 \right) = 1$$