Introduction

In the post Chat GPT world and in the era of automation, most Data Science practitioners, specially coming from a Non Computer Science background more often than not undermine the importance of raw coding.  The realization awakens when you develop a product from scratch with limited and expensive compute thus your written code needs to be optimize fully. The Master Method is a rule which helps to arrive at Code complexity for recursive algorithms. As a first step in the world of Data Structures and Algorithms, Code complexity and the Big  'O' notation are taught to learners.  This Explanatory note attempts to de mystify the math behind the Master Method Theorem / Rules.

Formulation

The standard form for Master Methods Big O notation  is given as follow:

Where

a = number of recursive calls >= 1

b = input size shrinkage factor > 1

d = exponent in summing time of "combine" step

Example : Binary Search in a Sorted Array

We shall look at how this method maybe applied to algorithms. We take as an example a very popular search algorithm namely the "Binary Search".  Where we search for a number in a sorted array with Time Complexity less than O(n)

The pseudo code for the same is given as

1. Initiate: n = array length; min = 0 , max = n -1 , set target value for search
2. Mid = integer ((min + max) / 2)
3. IF array[Mid] == target

                         PRINT ("Value = ", Target)

                         STOP

4. ELSE IF array[Mid] < target

                        SET min = mid + 1

                       STOP

5. ELSE

           Set max = mid -1

6. GOTO STEP 2

Now the Master Method formulation is designed for a recursive algorithm not a loop based one like above. So one has to now think in terms of Recursive Formulation in order to apply the Master Method

Recursive Implementation of Binary Search  function in a Sorted Array

def binary_search (array, target) :

       return bin_search_recursive(array, target, 0, len(array) -1 )

def bin_search_recursive(array, target, left, right)

       IF left > right :

           return -1

       Mid =  integer (left + right)/ 2)

       Value = array[mid]

       IF target == value:

           return Mid

       ELIF  target < value

           return bin_search_recursive(array, target, left, mid -1 )

       ELSE

           return bin_search_recursive(array, target, mid + 1, right)

Applying Master Method Parameters for recursive binary search

Parameter 'b'

 The size of the problem halves at each step , thus b = 2

Parameter 'a'

There is one recursive call , thus a = 1

Parameter 'd'

The 'combine' Ops are in constant time – thus d = 0

Thus summarizing we have the following   

Now applying Master Method, we have the following

For the Current example: 

This gives us

– Which is well known

Proof of the Master Method

Consider the recurrence relation

We shall create a Tree / Table to understand the time complexity and problem size at each level of iteration.

Level 0

At this stage the problem is of size 'n' for recursion. Also the summation / combination cost is

. We have only 1 problem at the root level.

Level 1

This is the first recursive call. Now we have the recursive problem size reduced to

.   Also at this stage the number of problems = 'a' .

The work done in summation / compilation at this iteration stage =  (number of sub problems) X (complexity level at this stage)

Level 'ith'

At this stage each sub problem is of size ( ). This is because at each level a reduction of size by a factor of 'b' occurs

The count of sub problems at this stage is .  The work done at this level in combination / summation would be = (nos of sub problems ) X complexity at this level

Last Level

As at each stage the problem size reduces from 'n' by a factor of 'b'. Thus the last level would be iteration number =

. Also at this stage the problem size is reduced to 1

The count of sub problems at the last level would then be

Thus the work done at this level is then = (nos of sub problems) X (size of sub problem)

NOTE:

We would want the time complexity to be written as the power of 'n' , thus for the last level we can write mathematically :

PROOF of the Above :

To Prove:

Thus using (A), (B) and (C) we have finally

Q.E.D

 Thus the work done at the last level is

Then the summation from (D) becomes

This Concludes our proof of the Master Method!

About the Author:

Dr Anish Roychowdhury is a Data Science Professional and Educator with a total career experience   of 20 plus  years across industry and academia. Having both taught in full time and part time roles at leading B Schools and have held leadership roles in multiple organizations He holds a Ph.D, in computational Micro Systems from  IISc Bangalore),  with a Master's Thesis in the area of Microfabrication, (Louisiana State University, USA) and an Undergraduate degree from  NIT Durgapur with published research in GA -Fuzzy applications to Medical Diagnostics. 

ACKNOWLEDGEMENTS

The Author wishes to Acknowledge, Mr Narasimha Karumanchi, Principal Software Engineering Manager at Microsoft, Founder and Self-Published Author at CareerMonk for his review and feedback on this explanatory note.