Как найти временную сложность этого алгоритма?

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); 
    } 
} 

Является ли его временной сложностью O (log n) или O (n)?

Пожалуйста, помогите мне.

Answer 1

Вы делаете O(N) звонки на номер multiply, где N == high - low на вызов верхнего уровня.

Э.Г. возьмите N=2^K для удобства. Вы возвращаетесь на уровень K до того, как попадете в корпус, где low==high. На каждом уровне у вас есть 2^(K-1) звонков. Они суммируют до N - 1 звонков (1 + 2 + 4 + ... + 64 = 127).

Для общего N поведение масштабирования является тем же самым, что вы можете доказать, используя Случай 1 из Master Theorem на основе рекурсивного отношения T(N) = 2 T (N/2) вашей функции.