PUERTA | PUERTA-CS-2004 | Pregunta 82

Sea A[1, …, n] una array que almacena un bit (1 o 0) en cada ubicación, y f(m) es una función cuya complejidad temporal es θ(m). Considere el siguiente fragmento de programa escrito en un lenguaje similar a C:

counter = 0;
for (i = 1; i < = n; i++)
{ 
      if (A[i] == 1) 
         counter++;
      else {
         f(counter); 
         counter = 0;
      }
}

La complejidad de este fragmento de programa es
(A) Ω(n ² )
(B) Ω(nlog n) y O(n ² )
(C) θ(n)
(D) O(n)

Respuesta: (C)
Explicación: Tenga en cuenta que dentro de la condición else, f() se llama primero, luego el contador se establece en 0.

Considere los siguientes casos:

a) All 1s in A[]: Time taken is Θ(n) as
                  only counter++ is executed n times.

b) All 0s in A[]: Time taken is Θ(n) as
                  only f(0) is called n times

c) Half 1s, then half 0s: Time taken is  Θ(n) as
                  only f(n/2) is called once.

Cuestionario de esta pregunta