Master Theorem for Decreasing Function

Recurrence Relation for Decreasing Function

Mathematically speaking, the master theorem provides a solution to the recurrence relation. Let's learn how we can find the recurrence relation for a decreasing function.

Suppose we have a program like this.

def test(n):
    if n > 0:
        for i in range(1, n+1):
            print(n)
        test(n-1)

If the test() function takes T(n) time to execute, then

Figure: Recurrence Relation for decreasing Function

From the image, we can say,

$$T(n)=T(n-1)+n+n+1$$
$$\phantom{}=T(n)=T(n-1)+(2n+1)$$
$$\phantom{}=T(n)=T(n-1)+n[usingfrequencycountmethodfor2n+1]$$

Solving Recurrence Relation with Master Theorem

To solve an equation using recurrence relation for a decreasing function, the function must be in the following format:

$$T(n)=aT(n-b)+f(n)$$
$$where,$$
$$f(n)=O(n^k),$$
$$a>0,b>0,$$
$$k\ge 0$$

Now, let's observe the equation for three different cases:

Case 1: a = 1

$$T(n)=O(n^{k+1})$$

Case 2: a > 1

$$T(n)=O(n^k{a}^{\frac{n}{b}})$$

Case 3: a < 1

$$T(n)=O(n^k)$$

Let's see some examples of the calculating time complexity of decreasing function.

Example 1

The recurrence relation of the decreasing function we previously wrote is:

$$T(n)=T(n-1)+n$$

Now let's calculate its time complexity using the master theorem.

Step 1: Comparing the recurrence relation with the general form.

The general form of T(n) is:

$$T(n)=aT(n-b)+O(n^k)$$

Step 2: Modifying recurrence relation to match the general form.

$$T(n)=1\ast T(n-1)+O(n^1)$$

Step 3: Finding a, b, and k checking if the master theorem is possible

a = 1
b = 1
k = 1

Since a > 0, b > 0, and $k\ge 0$, the master theorem is possible.

Step 4: Comparing a and 1 and applying the matching rule

Here,

a = 1
k = 1

Since a = 1, let's apply the formula to find the time complexity for this scenario.

$$T(n)=O(n^{k+1})$$
$$\phantom{}=O(n^{1+1})$$
$$\phantom{}=O(n^2)$$

Example 2

The recurrence relation of the dividing function we previously wrote is:

$$T(n)=2T(n-1)+1$$

Now let's calculate its time complexity using the master theorem.

Step 1: Comparing the recurrence relation with the general form.

The general form of T(n) is:

$$T(n)=aT(n-b)+O(n^k)$$

Step 2: Modifying recurrence relation to match the general form.

$$T(n)=2\ast T(n-1)+O(n^0)$$

Step 3: Finding a, b, and k checking if the master theorem is possible

a = 2
b = 1
k = 0

Since a > 0, b > 0, and $k\ge 0$, the master theorem is possible.

Step 4: Comparing a and 1 and applying the matching rule

Here,

a = 2
k = 0

Since a > 1, let's apply the formula to find the time complexity for this scenario.

$$T(n)=O(n^k{a}^{\frac{n}{b}})$$
$$\phantom{}=O(n^0{a}^{\frac{n}{1}})$$
$$\phantom{}=O(1\ast 2^n)$$
$$\phantom{}=O(2^n)$$

Example 3

The recurrence relation of the dividing function we previously wrote is:

$$T(n)=\frac{1}{2}T(n-1)+n^2$$

Now let's calculate its time complexity using the master theorem.

Step 1: Comparing the recurrence relation with the general form.

The general form of T(n) is:

$$T(n)=aT(n-b)+O(n^k)$$

Step 2: Modifying recurrence relation to match the general form.

$$T(n)=\frac{1}{2}\ast T(n-1)+n^2$$

Step 3: Finding a, b, and k checking if the master theorem is possible.

$$a=\frac{1}{2}$$
$$b=1$$
$$k=2$$

Since a > 0, b > 0, and $k\ge 0$, the master theorem is possible.

Step 4: Comparing a and 1 and applying the matching rule

Here,

$$a=\frac{1}{2}$$
$$k=2$$

Since a < 1, let's apply the formula to find the time complexity for this scenario.

$$T(n)=O(n^k)$$
$$\phantom{}=O(n^2)$$