Question

For each function below, write the recurrence relation for its running time and then use the Master Theorem to find its complexity.

int f(int arr[], int n) {
if (n == 0) {
return 0;
}
int sum = 0;
for (int j = 0; j < n; ++j)
return f(arr, n / 2) + sum + f(arr, n / 2);
}
Recurrence:
Complexity:

Answer 1

The function's recurrence relation is T(n) = 2T(n/2) + O(n), and by applying the Master Theorem, its running time complexity is determined to be O(n * log n).

Step-by-step explanation:

The function in question features a recursive call that splits its input array in half for each call, along with a linear traversal of 'arr' using a for loop. To determine the running time, we need to establish the recurrence relation and then apply the Master Theorem to solve for the function's complexity.

Recurrence Relation:

The function performs two recursive calls on subarrays of size ½ n and has a linear addition loop that runs in O(n). Therefore, the recurrence relation is:

T(n) = 2T(n/2) + O(n)

Applying the Master Theorem:

We apply the Master Theorem for divide-and-conquer recurrences with the following parameters: a=2, b=2, and f(n)=n. This situation falls into Case 2 of the Master Theorem where f(n) = θ(nlogba), implying that f(n) is asymptotically equal to n1, which is the same as nlog22. According to Case 2, the complexity of the function equates to:

O(n * log n)