Thanks bro. I was trying to relate it to merge sort. I was trying to visualize the recursion tree from root to the leaf node, but it was easy to apply the GP if visualized from leaf node to the root node, thereby making the maths like:

n + n/2 + n/4 ..... + 1

instead of:

1 + 2 + 4 + ...... + n (where the common difference is greater than 1 and is not converging.)

def f(x, y):
 
    # base case
 
    if (y == 0): 
 
        return 1
 
 
 
    # even y
 
    if (y % 2 == 0): 
 
        return f(x, y/2) * f(x, y/2) % 41 
 
 
 
    # odd y 
 
    if (y % 2 == 1): 
 
        return x * f(x, y/2) * f(x, y/2) % 41

Why is the complexity of the above code O(y) in the ...