Test: Recurrence Relations - Computer Science Engineering (CSE) MCQ

One easy way to solve this is to try putting different 
values of m.

For example, we know T(1) = 1. If we put m = 1, only A
and B satisfy the result.

m = 2

T(2) = T(1) + 1 = 2
T(3) = T(2) + 1 = 3
T(4) = T(3) + 2 = 5

Both A & B produce 5

m = 3
T(9) = T(4) + 2*5 + 1 = 5 + 10 + 1 = 16
Both A & B produce 16

m = 4
T(16) = T(9) + 3*7 + 1 = 16 + 21 + 1 = 38
Only B produces 38, A produces 34 which doesn't match 

We have T (2^k) = 3  T (2^k-1) + 1 = 3²  T (2^k-2) + 1 + 3 = 3³  T (2^k-3) + 1 + 3 + 9 . . . (k steps of recursion (recursion depth)) = 3^k  T (2^k-k) + (1 + 3 + 9 + 27 + ... + 3^k-1) = 3^k + ( ( 3^k - 1 ) / 2 ) = ( (2 * 3^k) + 3^k - 1 )/2 = ( (3 * 3^k) - 1 ) / 2 = (3^k+1 - 1) / 2 Hence, B is the correct choice.   Please comment below if you find anything wrong in the above post.

The recurrence is
T(x, y) = Θ(x+y) + T(x/2, y/2) 
It can be written as below.
T(x, y) = Θ(x+y) + Θ((x+y)/2) + Θ((x+y)/4) +  Θ((x+y)/8)  .....
T(x, y) = Θ((x+y) + (x+y)/2 + (x+y)/4 + (x+y)/8  ..... )
The above expression forms a geometric series with ratio as 2 and starting element as (x+y)/2 T(x, y) is upper bounded by Θ(x+y) as sum of infinite series is 2(x+y). It is lower bounded by (x+y)

a₁ = 8 a_n = 6n² + 2n + a_n-1   a_n = 6[n² + (n-1)²] + 2[n + (n-1)] + a_n-2   Continuing the same way till n=2, we get a_n = 6[n² + (n-1)² + (n-2)² + ... + (2)²] + 2[n + (n-1) + (n-2) + ... + (2)] + a₁   a_n = 6[n² + (n-1)² + (n-2)² + ... + (2)²] + 2[n + (n-1) + (n-2) + ... + (2)] + 8   a_n = 6[n² + (n-1)² + (n-2)² + ... + (2)²] + 2[n + (n-1) + (n-2) + ... + (2)] + 6 + 2   a_n = 6[n² + (n-1)² + (n-2)² + ... + (2)² + 1] + 2[n + (n-1) + (n-2) + ... + (2) + 1]   a_n = (n)*(n+1)*(2n+1) + (n)(n+1) = (n)*(n+1)*(2n+2)   a_n = 2*(n)*(n+1)*(n+1) = 2*(n)*(n+1)²   Now, put n=99. a₉₉ = 2*(99)*(100)² = 1980000 = K * 10⁴ Therefore, K = 198.   Thus, C is the correct choice.

Please note that the question is asking about exact solution. Master theorem provides results in the form of asymptotic notations. So we can't apply Master theorem here. We can solve this recurrence using simple expansion or recurrence tree method.

T(n) = √(2) T(n/2) + √n = √(2) [√(2) T(n/4) + √(n/2) ] + √n = 2 T(n/4) + √2 √(n/2) +√n = 2[ √2 T(n/8) + √(n/4) ]+√2 √(n/2)+√n = √(2^3) T(n/8)+ 2 √(n/4) + √2 √(n/2) +√n = √(2^3) T(n/8)+√n +√n +√n = √(2^3) T(n/(2^3))+3√n ............................................. = √(2^k) T(n/(2^k))+k√n = √(2^logn) + logn √n = √n + logn √n = √n(logn +1)

Alternate Solution : This question can be easily done by substitution method look: T(1)= 1; GIVEN. Now use n=2 in the given recurrence relation which gives 2*(1.414) (since value of root over 2 is 1.414) now by looking at the options use n=2 which satisfies option A.

Standard planning algorithms assume environment to be both deterministic and fully observable. So, option (A) is correct.

T(n) = 2T (n/2) + n = 2¹ T(n/2¹) + 1.n [ k = 1] = 2^k-1 T(n/2^k-1) + (k-1)n = 2^k-1 (2T(n/2^k + n/2^k-1) + (k-1)n = 2^k T(n/2^k) + kn

Option (A) is Correct.

F(n) = (n + f(n-1)) → n + (n-1 + f(n-2))→ n + (n-1 + (n-2 (+...+ (n-(n-1) + f(1))) Time complexity of of code is = O(n)

Given,

T(n) = T(n^1/a)+1, T(b) = 1

Now, using iterative method,

= T(n) = [T(n^1/a2)+1] + 1 = [T(n^1/a3)+1] + 2 = [T(n^1/a4)+1] + 3 . . . = [T(n^1/ak)+1] + (k-1) = T(n^1/ak) + k

Let,

→ n^1/ak = b → log(n^1/ak) = log(b) → a^k = log(n) / log (b) = log_b(n) → k = log_alog_b(n)

Therefore,

= T(n^1/ak) + k = T(b) + log_alog_b(n) = 1 + log_alog_b(n) = Θ(log_alog_b(n))

Option (A) is correct.

On comparing power of these given functions : f1 has n in power. f2 has logn in power. f3 has √n in power. Hence, f2, f3, f1 is in increasing order. Note that you can take the log of each function then compare.

Given, recurrence relation can be written as, T(n) = T(n/2) + T(2n/5) + 7n T(n) = T((5/2)n/5) + T(2n/5) + 7n Since, sum of numerator (5/2+2 = 4.5) is less than denominator (5), so time complexity would be function itself. Hence, T(n) = Θ(7n) = Θ(n)

Arithmetic operations performed by binary search on sorted data items means computation of mid element required arithmetic operation. So it will be computed log(n) time and Hence option (C) will be correct.

Following is the initial recursion tree for the given recurrence relation.

If we further break down the expression T(n/4) and T(n/2), we get following recursion tree.

Breaking down further gives us following

To know the value of T(n), we need to calculate sum of tree nodes level by level. If we sum the above tree level by level, we get the following series T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ....

The above series is geometrical progression with ratio 5/16 To get an upper bound, we can sum the above series for infinite terms. We get the sum as (n^2) / (1 - 5/16) which is O(n^2)

T(n) = cn + T(n/3)

= cn + cn/3 + T(n/9)

= cn + cn/3 + cn/9 + T(n/27)

Taking the sum of infinite GP series. The value of T(n) will be less than this sum.

T(n) = cn(1/(1-1/3))

= 3cn/2

or we can say

cn = T(n) = 3cn/2

Therefore T(n) = (n)

Change of variables: let m = lg n. Recurrence becomes S(m) = S(m/2) + θ(lgm). Case 2 of master’s theorem applies, so T(n) = θ( (log Log n) ^ 2).