Introduction

In the previous article, we learned how to solve a recurrence relation having one recursive term using the Substitution method, in this article, we will learn how to solve a recurrence relation having multiple recursive terms using the Recursive Tree approach. Let's first clarify what is meant by multiple recursive terms.

Example

How many recursive terms are there in this recurrence relation? In this case, T (n/5) and T (4n/5) are two recursive terms. It's that simple, right? Let's solve this recurrence relation and determine its time complexity.

Approach

Here we can see n placed as the head. Why? This is just a visualization of the flow of our recursion process. Let's thus split this n by (1/5) and (4/5). Did you get where we obtained those fractional figures? Yes, it comes from the recurrence relation.

Can you predict what the next step will be? Yes, we will repeat the process of dividing the node by (1/5) and (4/5). But we divide the previous result's node on each level. Let's see how that turns out.

You can go through as many steps as you like. For clarification, let's go one step further and look at it again

Cost of Splitting

The cost of doing the split at each level must be determined. How do we calculate the cost of splitting, then? The cost of splitting can be determined by simply summing the node values in the row. See how that goes.

Since all final values of each summation are n, we referenced one value. This is a simple addition process, but did you understand what the Cost of Splitting means? We will learn that when we discuss Divide and Conquer. As of now, the most important thing is to solve the problem

Assume that this recursive tree will expand to k times and examine its operation. Take into account the tree's left side as an example.

No need to worry, your eyes are fine, the blur was purposefully added. Focus on the left side.

Finding K

What is the objective of solving this equation? We must locate K. Therefore, to transform the equation in terms of K, we can take a logarithm on both sides. First, what should be the base of our logarithm? Let's see how that goes.

Likewise, let's compute for the right side as well.

According to the basic logarithmic property, what will be the highest value?

The right side has a larger value, why is that? Values are higher when the base is lower. We also need to multiply with n to get the final time complexity here because the cost of splitting is n per level.

Time Complexity

Congratulations on solving another recurrence relation. However, we did not write the pseudo code for this recurrence relation because it is an example of the Divide and Conquer approach. It will be covered in a later section. Happy learning