how to find the time complexity of this algorithm?

Question

int multiply(int a[],int low,int high,int modulus)
{
    if(low==high)
        return (a[low]);
    else
    {
       int mid = (low+high)/2;
       int x = multiply(a, low, mid, modulus) % modulus;
       int y = multiply(a, mid+1, high, modulus) % modulus;
       return ((x*y) % modulus);
    }
}

Is its time complexity O(log n) or it is O(n) ?

Please help me.

Answer 1

You are making O(N) calls to multiply, where N == high - low at the top-level call.

E.g. take N=2^K for convenience. You are recursing K levels deep before you hit the case where low==high. At each level, you have 2^(K-1) calls. They add up to a total of N - 1 calls (1 + 2 + 4 + ... + 64 = 127).

For general N the scaling behavior is the same, which you can prove using Case 1 of the Master Theorem based on the recursion relation T(N) = 2 T (N / 2) of your function.