comment trouver la complexité temporelle de cet algorithme?

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

Sa complexité temporelle est-elle O (log n) ou O (n)?

S'il vous plaît aidez-moi.

Answer 1

Vous effectuez O(N) appels à multiply, où N == high - low à l'appel de niveau supérieur.

E.g. Prenez N=2^K pour plus de commodité. Vous êtes récurant K niveaux avant de frapper le cas où low==high. À chaque niveau, vous avez 2^(K-1) appels. Ils totalisent N - 1 appels (1 + 2 + 4 + ... + 64 = 127). Le comportement de mise à l'échelle est le même que celui que vous pouvez prouver en utilisant le cas 1 de Master Theorem basé sur la relation de récurrence T(N) = 2 T (N/2) de votre fonction.