Master Theorem for Dividing Function

Recurrence Relation for Dividing 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 dividing function.

Suppose we have a program like this.

def test(n):
    if n > 0:
        print(n)
        test(n // 2)

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

Figure: Recurrence Relation for Dividing Function

From the image, we can say

$$T(n)=T\left(\frac{n}{2}\right)+1+1$$
$$\phantom{}=T\left(\frac{n}{2}\right)+2$$

In place of constant 2, we can write 1 or simply represent it with c.

$$T(n)=T\left(\frac{n}{2}\right)+1$$

Solving Recurrence Relation with Master Theorem

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

$$T(n)=\frac{a}{b}+f(n)$$
$$where,$$
$$f(n)=\text{Ө}(n^k(\log n{)}^p),$$
$$a\ge 1,b>1,$$
$$k\ge 1,$$
$$p=realnumber$$

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

• Case 1: ${\log }_{b}a>k$
• Case 2: ${\log }_{b}a=k$
• Case 3: ${\log }_{b}a<k$

${\log }_{b}a>k$

If ${\log }_{b}a>k$, then $T(n)=\text{Ө}(n^{{\log }_{b}a})$

${\log }_{b}a=k$

If ${\log }_{b}a=k$, then we should check values of p for three cases:

1. if p >-1, then $T(n)=\text{Ө}(n^k{\log }^{p+1}n)$
2. if p = -1, then $T(n)=\text{Ө}(n^k\log \log n))$
3. if p < -1, then $T(n)=\text{Ө}(n^k)$

${\log }_{b}a<k$

If ${\log }_{b}a<k$, then we should check values of p for two cases:

1. if $p\ge 0$, then $T(n)=\text{Ө}(n^k{\log }^{p}n))$
2. if p < 0, then $T(n)=\text{Ө}(n^k)$

Example 1

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

$$T(n)=T\left(\frac{n}{2}\right)+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\left(\frac{n}{b}\right)+\text{Ө}(n^k(\log n{)}^p))$$

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

$$T(n)=1\ast T\left(\frac{n}{2}\right)+\text{Ө}(n^0(\log n{)}^0)$$

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

a = 1
b = 2
k = 0
p = 0

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

Step 4: Comparing ${\log }_{b}a$ and k and applying the matching rule.

Here,

$${\log }_{b}a={\log }_{2}1=0$$
$$k=0$$

Since ${\log }_{b}a=k$ and p > -1, let's apply the formula to find the time complexity for this scenario.

$$T(n)=\text{Ө}(n^k{\log }^{p+1}n)$$
$$\phantom{}=\text{Ө}(n^0{\log }^{0+1}n)$$
$$\phantom{}=\text{Ө}(1\ast {\log }^{1}n)$$
$$\phantom{}=\text{Ө}(\log n)$$

Example 2

Suppose we have the following recurrence relation:

$$T(n)=4T\left(\frac{n}{2}\right)+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\left(\frac{n}{b}\right)+\text{Ө}(n^k(\log n{)}^p)$$

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

$$T(n)=4T\left(\frac{n}{2}\right)+\text{Ө}(n^1(\log n{)}^0)$$

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

a = 4
b = 2
k = 1
p = 0

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

Step 4: Comparing ${\log }_{b}a$ and k and applying the matching rule.

Here,

$${\log }_{b}a={\log }_{2}4=2$$
$$k=1$$

Since ${\log }_{b}a>k$, let's apply the formula to find the time complexity for this scenario.

$$T(n)=\text{Ө}(n^{{\log }_{b}a})$$
$$\phantom{}=\text{Ө}(n^2)$$

Example 3

Suppose we have the following recurrence relation:

$$T(n)=2T\left(\frac{n}{2}\right)+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\left(\frac{n}{b}\right)+\text{Ө}(n^k(\log n{)}^p)$$

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

$$T(n)=2\ast T\left(\frac{n}{2}\right)+\text{Ө}(n^2(\log n{)}^0)$$

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

a = 2
b = 2
k = 2
p = 0

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

Step 4: Comparing ${\log }_{b}a$ and k and applying the matching rule.

Here,

$${\log }_{b}a={\log }_{2}2=1$$
$$k=2$$

Since ${\log }_{b}a$ and $p\ge 0$, let's apply the formula to find the time complexity for this scenario.

$$T(n)=\text{Ө}(n^k(\log n{)}^p)$$
$$\phantom{}=\text{Ө}(n^2(\log n{)}^0)$$
$$\phantom{}=\text{Ө}(n^2\ast 1)$$
$$\phantom{}=\text{Ө}(n^2)$$

Example 4

Suppose we have the following recurrence relation:

$$T(n)=2T\left(\frac{n}{2}\right)+\text{Ө}(n^2{\log }^{2}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\left(\frac{n}{b}\right)+\text{Ө}(n^k(\log n{)}^p)$$

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

$$T(n)=2T\left(\frac{n}{2}\right)+\text{Ө}(n^2(\log n{)}^2)$$

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

a = 2
b = 2
k = 2
p = 2

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

Step 4: Comparing ${\log }_{b}a$ and k and applying the matching rule.

Here,

$${\log }_{b}a={\log }_{2}2=1$$
$$k=2$$

Since ${\log }_{b}a<k$ and $p\ge 0$, let's apply the formula to find the time complexity for this scenario.

$$T(n)=\text{Ө}(n^k(\log n{)}^p)$$
$$\phantom{}=\text{Ө}(n^2(\log n{)}^2)$$
$$\phantom{}=\text{Ө}(n^2{\log }^{2}n)$$