Master formula. (used to calculate the time complexity of recursion.)

One 、Mster The formula

Prerequisite ：

• The size of the recursive subproblem must be the same .

Now let me explain , The specific meaning of this formula .
First a Is the number of calls on the scale of a subproblem of a recursive problem ,d Is the number of subproblems , hinder N Of d The power is the call except for the recursive subproblem , The time complexity of the scale of other problems .

for instance ：

def func(arr, l, r):  #  Again arr The largest value found in the array 
    if l == r:
        return  arr[l]
    mid = l + ((r - l) >> 1)
    l_max = func(arr, l, mid)
    r_max = func(arr, mid + 1, r)
    return max(l_max, r_max)

For example, the above code is a simple recursion .
Well, its T（N） = 2 * T（N / 2） + O（1）
Because every time you call the main function , You need to call the function of the subproblem with the same scale twice , So for 2 * T（N / 2）, And because it calls functions of subproblems , Other time complexity is O（1）. So this is the recursive Master The formula .

Two 、 Time complexity of calculation

According to this formula and our code above , The time complexity should be O（N）