Calculating Time complexity of Divide and Conquer recurrence using Akra-Bazzi Method

Hey everyone! Welcome back to another article of mine, I hope you're doing great. So today in this blog I will teach you how to calculate the time complexity of divide and conquer recurrence using the Akra-Bazzi method. I am assuming that you already have some idea of Algorithms. So let's begin!

Firstly, what is Divide and Conquer?

Divide and conquer is an algorithmic paradigm that involves breaking down a problem into smaller subproblems, solving each subproblem independently, and then combining the solutions of the subproblems to find the solution of the original problem. This approach is often used for solving problems that are too complex to be solved straightforwardly. One example of Divide and Conquer is Binary search using recursion. I already have an article on it you can check it out if you want, or else I would be attaching the code here anyways you can go through it once.

Java program for binary search using recursion

static int binary(int[] arr, int target, int start, int end) {
        int mid = start + (end - start) / 2;
        if (target == arr[mid]) {
            return mid;
        }

        if (target < arr[mid]) {
            return binary(arr, target, start, mid - 1);
        }

        return binary(arr, target, mid + 1, end);
    }

Moving on, let's look how a divide and conquer recurrence looks like!

Form of Divide and Conquer Recurrence relation

Divide and Conquer recurrence looks like the one in the image below. Don't worry it may be overwhelming further, just look at the formulae. I will explain how these formulae will be used when we solve questions.

Some examples of Divide and Conquer Recurrence relation :

Now how to calculate the complexity of these recurrence relations? Here comes the Akra-Bazzi method!

AKRA-BAZZI METHOD

The image below is the formula for Akra-Bazzi Method

How to calculate 'p'?

To calculate the value of 'p' we use the relation in the image below.

Now let's solve some questions for understanding how the above formulae will be used.

Question 1 :

But there is a problem! What if you are unable to guess the value of 'p' what then? Let's look at this problem.

What if you can't find the value of 'p'

We will understand it using a question.

Woo! Hoo!

That's it! Now you can solve any Divide and Conquer complexity question. For your practice, you can try this question.

If you are still here! You can follow me on Twitter. You can like the blog and follow me on Hashnode as well. Till then goodbye! I will see you very very soon.