Question

Solve both the bits and explain the procedure and steps to

solving the question
Solve the following recurrence relations
i) T(n)=8 T(n / 2)+n^{2} for n>2, T(2)=1 solve for ( n=2^{k})
ii) x(n)=x(n-1)+n for ( n>0, x(0)=0 )

Answer 1

To solve the given recurrence relations, we use the substitution method and solve for the unknown variables. The first recurrence relation, T(n) = 8T(n/2) + n^2, has a solution of T(n) = n^k + n^2. The second recurrence relation, x(n) = x(n-1) + n, has a solution of x(n) = n(n+1)/2.

Step-by-step explanation:

To solve the recurrence relation T(n) = 8T(n/2) + n^2, we can use the substitution method. Let's assume T(n) = O(n^k) for some constant k. Substituting this assumption into the recurrence relation, we get:

T(n) = 8T(n/2) + n^2 = 8(n/2)^k + n^2 = 8(n^k/2^k) + n^2.

Simplifying further, we get T(n) = n^k + n^2. Since this must hold for all n, we can equate the exponents and solve for k to find the value of k.

Plugging in the value of k in the assumed solution T(n) = O(n^k), we get the final solution for the given recurrence relation.

Using this procedure, we can similarly solve the second recurrence relation x(n) = x(n-1) + n. The solution for this recurrence relation is x(n) = n(n+1)/2.