Big O para while loops

Question

El otro día tuve esta pregunta para mi tarea, pero todavía no estaba seguro de si tenía razón.

for(int i =1; i <n; i++) //n is some size 
{    
    for(j=1; j<i; j++) 
    { 
     int k=1; 

     while (k<n) 
     { 
      k=k+C; //where C is a constant and >=2 
     } 
    } 
} 

sé que el anidado para los bucles es O (n^2), pero no estaba segura con el bucle while. Supuse que todo el código sería O (n^3).

Answer 1

int k=1; 

    while (k<n){ 
     k=k+C     //where C is a constant and >=2 
    } 

Esto se llevará a (n-1)/C pasos: escribir u = (k-1)/C. Entonces, k = Cu + 1 y la declaración se convierte en

u=0; 
while(u < (n-1)/C) { 
    u=u+1 
} 

De ahí que el bucle while es O(n) (ya C es constante)

EDIT: voy a tratar de explicarlo a la inversa.

Comience con una variable ficticia u. El ciclo

u=0; 
while(u < MAX) { 
    u = u+1 
} 

ejecuta MAX veces.

Cuando dejas MAX = (n-1)/C, el bucle es

u=0; 
while(u < (n-1)/C) { 
    u=u+1 
} 

Y que corre (n-1)/C veces.

Ahora, el cheque u < (n-1)/C es equivalente a C*u < n-1 o C*u + 1 < n, por lo que el bucle es equivalente a

u=0; 
while(C*u + 1 < n) { 
    u=u+1 
} 

Ahora, supongamos que reescribimos este bucle en función de una variable k = C * u + 1. Entonces,

u=0; 
k=1; // C * 0 + 1 = 1 

El bucle se parece

while(C*u + 1 < n) { 
while(k < n) { 

y la condición interna es

u=u+1 
    k=k+C //C * (u+1) + 1 = C * u + 1 + C = old_k + C 

Poniendo todo junto:

int k=1; 

    while (k<n){ 
     k=k+C 
    } 

toma (n-1)/C pasos.

Answer 2

El bucle interior es literalmente O(n/C)=O(n), así que sí, que en general es O(n^3) (el segundo bucle tiene un límite superior de O(n))

Answer 3

Bueno, lo que tendría que mirar el número de veces que el cuerpo del bucle mientras se ejecuta por un valor dado de ny C. Por ejemplo, n es 10 y C es 3. El cuerpo corre 3 veces: k = 1, k = 4, k = 7. Para n = 100 y C = 2, el cuerpo correría 50 veces: k = 1,3,5,7,9, ..., 91,93,95,97,99. Es una cuestión de contar por C hasta n. Debería poder calcular la complejidad de Big-O a partir de esa pista.

Answer 4

Formalmente, puede proceder utilizando la siguiente metodología (Sigma Notation):

Dónde a simboliza el número de operaciones constantes en el interior del bucle más interior (a = 1 si desea contar el número exacto de iteraciones).