Divide and Conquer Strategy and Recurrence Relations in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to correctly divide the problem size by 2 in the recursive call.

DSA C

int divideAndConquer(int n) {
    if (n <= 1) return n;
    return divideAndConquer(n [1] 2) + n;
}

Drag options to blanks, or click blank then click option'

A-

B+

C/

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or subtraction instead of division to reduce problem size.

Multiplying n instead of dividing.

The divide and conquer strategy often splits the problem size in half, so dividing n by 2 is correct.

2fill in blank

medium

Complete the recurrence relation formula for the time complexity T(n) = 2 * T(n {{BLANK_1}} 2) + n.

DSA C

T(n) = 2 * T(n [1] 2) + n

Drag options to blanks, or click blank then click option'

A/

B+

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of division in the recurrence relation.

Using addition which increases problem size.

The recurrence relation divides the problem size by 2, so the operator is division '/'.

3fill in blank

hard

Fix the error in the recursive function call to correctly implement divide and conquer.

DSA C

int solve(int n) {
    if (n <= 1) return 1;
    return 2 * solve([1]) + n;
}

Drag options to blanks, or click blank then click option'

An * 2

Bn / 2

Cn + 2

Dn - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Multiplying or adding to n instead of dividing.

Using n - 1 which reduces size by 1, not half.

The problem size should be divided by 2 in the recursive call to correctly apply divide and conquer.

4fill in blank

hard

Fill both blanks to complete the recurrence relation and base case for a divide and conquer algorithm.

DSA C

if (n [1] 1) return 1;
T(n) = 3 * T(n [2] 3) + n;

Drag options to blanks, or click blank then click option'

A<=

B>

C/

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using greater than in base case condition.

Using subtraction instead of division in recurrence.

The base case checks if n is less than or equal to 1, and the recurrence divides n by 3.

5fill in blank

hard

Fill all three blanks to complete the recursive function and recurrence relation for a divide and conquer algorithm.

DSA C

int dcFunc(int n) {
    if (n [1] 1) return 1;
    return 4 * dcFunc(n [2] 2) + n * n;
}

T(n) = 4 * T(n [3] 2) + n * n;

Drag options to blanks, or click blank then click option'

A<=

B-

C/

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication or subtraction instead of division.

Incorrect base case condition.

The base case uses <= 1, and the recursive calls divide n by 2 in both function and recurrence.