3 Calculate The Running Time of The Following Recursive Function

Introduction

Recursive functions break problems into smaller subproblems, solving them and combining the results. The running time of a recursive function depends on how many subproblems are created and how they are solved.

To calculate the running time, we use the Master Theorem or solve recurrence relations. These methods help us determine the time complexity in terms of Big-O notation.

Master Theorem

The Master Theorem provides a straightforward way to solve recurrences of the form:

Where:

• a is the number of subproblems
• b is the factor by which the problem size is reduced
• f(n) is the cost of dividing the problem and combining the results

The Master Theorem has three cases:

1. If f(n) = O(n^{log_ba - ε}) for some ε > 0, then T(n) = Θ(n^log_ba)
2. If f(n) = Θ(n^log_ba), then T(n) = Θ(n^log_ba log n)
3. If f(n) = Ω(n^{log_ba + ε}) for some ε > 0, and if af(n/b) ≤ kf(n) for some k < 1 and all sufficiently large n, then T(n) = Θ(f(n))

Recurrence Relations

When the Master Theorem doesn't apply, we solve recurrence relations using substitution, recursion trees, or the Akra-Bazzi method.

Common recurrence relations include:

• Linear recurrence: T(n) = T(n-1) + c
• Divide-and-conquer: T(n) = aT(n/b) + f(n)
• Multiple recurrence: T(n) = T(n-1) + T(n-2) + c

For example, the recurrence T(n) = 2T(n/2) + n can be solved using the Master Theorem to find T(n) = Θ(n log n).

Examples

Let's calculate the running time for the following recursive function:

Using the Master Theorem:

• a = 4, b = 2, f(n) = n²
• log_ba = log₂4 = 2
• Compare f(n) to n^log_ba = n²
• Since f(n) = Θ(n²), we use Case 2
• Therefore, T(n) = Θ(n² log n)

Another example:

Using the Master Theorem:

• a = 3, b = 4, f(n) = n
• log_ba = log₄3 ≈ 0.792
• Compare f(n) to n^log_ba ≈ n^0.792
• Since n is polynomial and n^0.792 is polynomial, but n grows faster than n^0.792, we use Case 3
• Therefore, T(n) = Θ(n)