Algoritmos | Análisis de Algoritmos | Pregunta 8

¿Cuál es la complejidad temporal de la siguiente función?

void fun(int n, int arr[])
{
    int i = 0, j = 0;
    for(; i < n; ++i)
        while(j < n && arr[i] < arr[j])
            j++;
}

(A) O(n)
(B) O(n^2)
(C) O(nlogn)
(D) O(n(logn)^2)

Respuesta: (A)
Explicación: A primera vista, la complejidad del tiempo parece ser O(n^2) debido a dos bucles. Pero, tenga en cuenta que la variable j no se inicializa para cada valor de la variable i . Entonces, el bucle interno se ejecuta como máximo n veces. Por favor observe la diferencia entre la función dada en cuestión y la siguiente función:

void fun(int n, int arr[])
{
    int i = 0, j = 0;
    for(; i < n; ++i)
    {
        j = 0;
        while(j < n && arr[i] < arr[j])
            j++;
    }
}