Recent questions tagged recurrence-relation

Which of the following is correct solution of the given recurrence relation? $T(n)=3 T(n / 4)+n \log n$$\theta(n \log n)$$\theta\left(n^{2} \log n\right)$$\theta\left(n(\...

Consider that the quick sort algorithm is used to sort an array of $n$ distinct randomly ordered elements. In every call, the pivot is chosen as the first element of the ...

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $\Theta(n)$?$T(n)=T(n-1)+1, \quad T(1)=1$$T(n)=2 T\left(\frac{n}{2...

Consider the following:For all $n>1$$$\begin{aligned}& T_1(n)=4 T_1(n / 2)+T_2(n) \\\\& T_2(n)=5 T_2(n / 4)+\theta\left(\log _2 n\right)\end{aligned}$$Assume that for all...

A recurrence arises in the problem: Number of ways to tile a 3×n rectangle with 2×1 dominoes (dominoes can be placed vertically or horizontally). Let T(n)​ be this number...

Consider the following recurrence relation describing the running time of an algorithm: $$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$$$(Base\ condition: T(1) =...

What will be the time complexity of T(n)= 3T(n-1) +n a)Theta (3^n) or b)Theta (n*3^n)

How to check if f(n) is polynomially greater than g(n)?

The tight asymptotic bound for the recurrence $T(n)=2 T(n / 4)+\sqrt{n}$ is$\Theta(\sqrt{n})$$\Theta(n \log n)$$\Theta(\sqrt{n} \log n)$$\Theta(n \log \sqrt{n})$

Which of the following is the solution of the following recurrence relation $\mathrm{T}( \mathrm{n})=\mathrm{T}(2 \mathrm{n} / 3)+1$?$\theta\left(n^{2}\right)$$\theta\lef...

Consider the function in $C$ code:Cal(a,b) { if (b!=1) { if (a!=1) { printf("*"); Cal(a/2, b); } else { b=b-1; Cal(10,b); } }}How many times $*$ is going to be printed, i...

Arrange the following recurrence relations in increasing order of their time capacity.$\mathrm{T}(\mathrm{n})=\mathrm{T}(\mathrm{n} / 2)+1$$\mathrm{T}(\mathrm{n})=2 \math...

Match List - I with List - II.$\begin{array}{llll} & \textbf{List - I} & & \textbf{List-II} \\ & \textbf{(Recurrence Relations)} && \textbf{(Complexity)} \\ \text{(A)}& \...

Let $S = \sum_{n\geq1} \dfrac{1}{n^2}$ and $A = \sum_{n\geq1}(-1)^{n+1}\dfrac{1}{n^2}$. Then which of the following statements is true?$S$ converges but $A$ does not conv...

Consider the following recurrence: $A_n$ is the sum of $A_{n-1}$ and a number chosen uniformly at random from {$1,...,n$}, starting from $A_0 :=1$. What is the expected v...

Starting with $x_0 = 0$, suppose you do the following:, at the $n^{th}$ stepyou flip a fair coin: if it is heads then $x_n := x_{n-1} + 1$ and if it is tails then $x_n :=...

Consider the rational number $a_n$ defined recursively as $a_n$ = $\dfrac{1}{1 + a_{n-1}}$, where $a_0 := 0$. Let $F_n$ denote the $n^{th}$ fibonacci number, where $F_0 :...

Consider the following recurrence relation:$$ T(n)=2 T(n-1)+n 2^{n} \text { for } n>0, \quad T(0)=1$$Which ONE of the following options is CORRECT?$T(n)=\Theta\left(n^{2}...