All questions of Recurrence Relations for Computer Science Engineering (CSE) Exam

Solution:

To solve the recurrence equation T(2k) = 3 T(2k-1) - 1, we need to find a pattern in the terms and then find a closed-form solution.

Pattern of Terms:
Let's find the values of T(1), T(2), T(4), T(8), T(16), and T(32) to observe a pattern:

T(1) = 1
T(2) = 3 T(1) - 1 = 3(1) - 1 = 2
T(4) = 3 T(2) - 1 = 3(2) - 1 = 5
T(8) = 3 T(4) - 1 = 3(5) - 1 = 14
T(16) = 3 T(8) - 1 = 3(14) - 1 = 41
T(32) = 3 T(16) - 1 = 3(41) - 1 = 122

We can observe that the terms are increasing rapidly, but there doesn't seem to be a clear pattern.

Finding a Closed-Form Solution:
Let's try to find a closed-form solution for T(k) by substituting k = 2^m:

T(2^m) = 3 T(2^m-1) - 1

Let's divide both sides by T(2^m-1):

T(2^m) / T(2^m-1) = 3 - 1 / T(2^m-1)

Since T(2^m) / T(2^m-1) is a ratio of consecutive terms, it should approach a constant value as m increases.

Let's assume the ratio approaches a constant value R:

R = 3 - 1 / R

Simplifying the equation:

R^2 = 3 - 1

R^2 = 2

Taking the square root of both sides:

R = √2

Now, let's express T(2^m) in terms of m using the formula T(k) = R^(m-1) T(2):

T(2^m) = √2^(m-1) T(2)

Substituting k = 2^m:

T(k) = √2^(log2(k)-1) T(2)

Simplifying:

T(k) = 2^(log2(k)/2 - 1/2) T(2)

Since T(2) = 2 - 1 / 2 = 1/2:

T(k) = 2^(log2(k)/2 - 1/2) / 2 = (2^(log2(k)/2 - 1/2) - 1) / 2

Simplifying further:

T(k) = (2^(log2(k)/2) - 2^(-1/2)) / 2

T(k) = (2^(log2(k)/2) - 1) / 2

Finally, let's substitute k = 2k to get the solution in terms of k:

T(2k) = (2^(log2(2k)/2) - 1) / 2

T(

Worst-case number of arithmetic operations in recursive binary search:
Binary search is a divide and conquer algorithm that searches for a target value within a sorted array. In the worst-case scenario, the target value is not present in the array, leading to the maximum number of comparisons.

Reasoning:
- In each recursive call of binary search, the array is divided into two halves.
- This process continues until the target value is found or the subarray size becomes 0.
- In the worst-case scenario, the target value is not present in the array, and the recursion reaches the base case with a single element or an empty subarray.

Analysis:
- At each step of the recursion, the algorithm performs a constant number of arithmetic operations to calculate the mid-point and compare the target value.
- The number of recursive calls required to reduce the array size to 1 in the worst-case scenario is logarithmic with respect to the size of the array (log2(n)).
- Hence, the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n is Theta(n) due to Theta(n) comparisons in the worst case.
Therefore, the correct answer is option 'C' - Theta(n^2).

To solve the given recurrence relation and find the value of k in a99 = k x 104, we can use the method of iteration.

1. Finding the pattern:
Let's find the values of a2, a3, a4, and a5 using the given recurrence relation:
a2 = 6(2^2) - 2(2) + a1 = 24 - 4 + 8 = 28
a3 = 6(3^2) - 2(3) + a2 = 54 - 6 + 28 = 76
a4 = 6(4^2) - 2(4) + a3 = 96 - 8 + 76 = 164
a5 = 6(5^2) - 2(5) + a4 = 150 - 10 + 164 = 304

By observing the pattern, we can see that the values of a2, a3, a4, a5 are 28, 76, 164, and 304 respectively.

2. Writing the general term:
From the pattern, we can deduce that the general term of the given recurrence relation can be written as:
an = 6n^2 - 2n + (n-1)^2 + 4

3. Finding the value of a99:
Using the general term, we can find the value of a99:
a99 = 6(99^2) - 2(99) + (99-1)^2 + 4
= 6(9801) - 198 + 98^2 + 4
= 58806 - 198 + 9604 + 4
= 68816

4. Finding the value of k:
Given that a99 = k x 104, we can equate the two expressions:
68816 = k x 104
k = 68816 / 104
k ≈ 661.538

Rounded to the nearest whole number, k ≈ 662.

Therefore, the value of k is approximately 662, which corresponds to option C.