recurrence-relation

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)$ ?

Which one of the following options is correct for the given data in the table?

Consider the following recurrence relation: T(n) = 2T(n - 1) + n2^n for n > 0, T(0) = 1. Which ONE of the following options is CORRECT?

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

Which one of the following options is correct for the given data in the table? Iteration ($i$) 0 1 2 3 Input ($I$) 20 $-$4 10 15 Output ($X$) 20 16 26 41 Output ($Y$) 20 $-$80 $-$8...

Let T(n) be the recurrence relation defined as follows: T(0) = 1, T(1) = 2, and T(n) = 5T(n - 1) – 6T(n-2) for n ≥ 2 Which one of the following statements is TRUE?

Consider the following recurrence relation: $T(n) = \begin{cases} \sqrt{n}T(\sqrt{n}) + n & \text{for } n \geq 1, \\ 1 & \text{for } n = 1. \end{cases}$ Which one of the following...

Consider the following recurrence relation: $$T(n) = \begin{cases} \sqrt{n} T(\sqrt{n}) + n & \text{for } n \ge 1, \\ 1 & \text{for } n = 1. \end{cases}$$ Which one of the followin...

Consider the following C function definition. int f(int x, int y) { for (int i=0; i<y; i++) { x=x+x+y; } return x; } Which of the following statements is/are TRUE about the above f...

Let $T(n)$ be the recurrence relation defined as follows: $T(0) = 1$ $T(1) = 2$, and $T(n) = 5T(n - 1) - 6T(n - 2)$ for $n \geq 2$ Which one of the following statements is TRUE?

A series of natural numbers $$F_1,F_2,F_3,F_4,F_5,F_6,F_7,\,.....$$ obeys $$F_{n+1}=F_n+F_{n-1}$$ for all integers $$n\ge2$$. If $$F_6=37$$, and $$F_7=60$$, then what is $$F_1$$ ?

The Lucas sequence $$L_n$$ is defined by the recurrence relation: $${L_n} = {L_{n - 1}} + {L_{n - 2}}$$, for $$n \ge 3$$, with $${L_1} = 1$$ and $${L_2} = 3$$. Which one of the opt...

Consider the following recurrence : f(1) = 1; f(2n) = 2f(n) $$-$$ 1, for n $$\ge$$ 1; f(2n + 1) = 2f(n) + 1, for n $$\ge$$ 1; Then, which of the following statements is/are TRUE?

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)$$...

Consider the following recurrence relation. $$T(n) = \left\{ {\begin{array}{*{20}{c}} {T(n/2) + T(2n/5) + 7n \ \ \ if\ n > 0}\\ {1\ \ \ \ \ \ \ if\ n = 0} \end{array}} \right.$$ Wh...

For parameters a and b, both of which are $$\omega \left( 1 \right)$$, T(n) = $$T\left( {{n^{1/a}}} \right) + 1$$, and T(b) = 1. Then T(n) is

Consider the recurrence function T(n) = { 2T(√n) + 1, n > 2; 2, 0 < n ≤ 2. Then T(n) in terms of Θ notation is

Consider the recurrence relation $${a_1} = 8,\,{a_n} = 6{n^2} + 2n + {a_{n - 1}}.$$ Let $${a_{99}} = K \times {10^4}.$$ The value of $$K$$ is ____________.

Let $${a_n}$$ be the number of $$n$$-bit strings that do NOT contain two consecutive $$1s.$$ Which one of the following is the recurrence relation for $${a_n}$$?

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( $$ \ge 2$$ ) numbers? In the recurrence equation...

Let $${a_n}$$ represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for $${a_n}$$?

A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4-pennant. The set of all possibl...

Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre specified pair...

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 recurrence relation capturing the optional execution time of the Towers of Hanoi problem with $$n$$ discs is

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0:n−1] is given below. Let L i , denote the length of the longest monotoni...

Consider a database table T containing two columns X and Y each of type integer. After the creation of the table, one record (X = 1, Y = 1) is inserted in the table. Let MX and MY...

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respe...

In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

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...

Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contains no consecutive $$0s$$. Which of the following recurrences does $${x_n}$$ satisfy?

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the...

When $$n = {2^{2k}}$$ for some $$k \ge 0$$, the recurrence relation $$$T\left( n \right) = \sqrt 2 T\left( {n/2} \right) + \sqrt n ,\,\,T\left( 1 \right) = 1$$$ evaluates to

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a 1 ,a 2 ,a 3 ,…,a n } and positive integer W, is there a subset of S whose elements sum to W...

Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contain no consecutive $$0s$$. The value of $${x_5}$$ is

What is the time complexity of the following recursive function? int DoSomething(int n){ if(n <= 2) return 1; else return (floor(sqrt(n)) + n); }

The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?

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?

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number...

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{ no. of lea...

The time complexity of the following C function is (assume n > 0) int recursive(int n){ if(n == 1){ return (1); } return (recursive(n - 1) + recursive(n - 1)); }

The recurrence equation T(1) = 1 T(n) = 2T(n - 1)+n, $$n \ge 2$$ Evaluates to

The recurrence equation $$\,\,\,\,\,\,\,T\left( 1 \right) = 1$$ $$\,\,\,\,\,\,T\left( n \right) = 2T\left( {n - 1} \right) + n,\,n \ge 2$$ evaluates to

The running time of the following algorithm Procedure A(n) If n<=2 return (1) else return (A([$$\sqrt n $$])); is best described by

The solution to the recurrence equation T(2 k ) = 3 T(2 k-1 ) + 1, T (1) = 1, is:

Consider the following C program: void abc(char *s) { if(s[0]=='\0') return; abc(s+1); abc(s+1); printf("%c",s[0]); } main() { abc("123"); } (a) What will be the output of the prog...

The solution to the recurrence equation $$T\left( {{2^k}} \right)$$ $$ = 3T\left( {{2^{k - 1}}} \right) + 1$$, $$T\left( 1 \right) = 1$$ is:

Solve the following recurrence relation $$\,\,\,\,\,\,\,{x_n} = 2{x_{n - 1}} - 1\,\,n > 1$$ $$\,\,\,\,\,\,\,{x_1} = 2$$

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

The recurrence relation that arises in relation with the complexity of binary search is:

Express T(n) in terms of the harmonic number H n = $$\sum\limits_{t = 1}^n {1/i,n \ge 1} $$ where T(n) satisfies the recurrence relation, T(n) = $${{n + 1} \over 2}$$ T(n-1) + 1, f...

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

Find a solution to the following recurrence equation T(n) = T(n - 1)+ n T(1) = 1

Solve the recurrence equations T (n) = T (n - 1) + n T (1) = 1

(a) Solve the recurrence equations $$\,\,\,\,\,\,\,\,\,T\left( n \right) = T\left( {n - 1} \right) + n$$ $$\,\,\,\,\,\,\,\,\,T\left( 1 \right) = 1T$$ (b) What is the generating fun...