Problema complexitate

[•skull]

Pseudocod:

Cod:

m = n;
s = 0;
while n >= 1 {
   m = m * 2;
   for i = 1 ... m {
      s = s + i;
   }
   n = [n/2];
}

Trebuie determinat timpul de executie in functie de n(notatie-theta).
Am avut problema asta la tema si au aparut fel si fel de capete luminate cu fel si fel de pareri(solutiile variand in special intre theta(n²) si theta(n²log n)). Voi ce parere aveti?

[•laurion]

2*(n-1)*n -> O(n²)

[•MciprianM]

For-ul interior executa m instructiuni, unde m ia valori, pe rand: 2*n, 4*n, 8*n, ..., 2^k * n unde k este de cate ori se executa corpul while-ului. Adica k = 1+ floor (log n). De unde timpul total de executie Theta (2*n + 4 * n + 2^k * n) = Theta (n^2). k este egal cu numarul de biti din scrierea lui n in baza 2. Impartirea la 2 este echivalenta cu o shiftare la dreapta. In suma dai factor comun pe n si ramane sa calculezi suma unei progresii geometrice.