¿Qué estoy haciendo mal al determinar el big-O de estas funciones Java?

Creo que lo hiciste bien para 1,2, 4.

Para el número 3:

El bucle externo solo funciona 3 veces (n – 3) – (n – 1) + 1.
El bucle interno todavía pasa por n.
Entonces es O (3n). Todavía en)

Para los ejemplos 1 y 2, su análisis es correcto. Para el ejemplo 3, el bucle externo es en realidad un bucle que siempre hará 3 iteraciones, lo que lo convierte en O (1). Por ejemplo 4, su análisis es correcto nuevamente. El hecho de que haya bucles anidados no significa necesariamente que algo será O (n ^ 2). Es muy importante observar los límites del bucle.

Ya veo lo que estás haciendo.

1. Cualquier operación individual se considera O (1): esto es correcto.
2. En caso de bucles anidados, multiplique la complejidad del bucle interno con la externa. – corrija nuevamente, ejemplos 2 y 4.
3. Siempre que haya una iteración que implique ‘n’, debe ser O (n), incorrecto aquí. Este es el ejemplo 3. Mire las iteraciones del bucle externo, va de n-3 a n-1, que son solo 3 pasos, por lo tanto, la complejidad total se convierte en 3 veces la complejidad del bucle interno. Que es 3 * n => O (n)

La siguiente complejidad del bucle sigue siendo O (1)

var n = 100000;
para (i = 1; i {
Console.Writeline (i);
}

Porque tienes los límites definidos.

Espero que captes la idea.

Ejemplo 3

El primer ciclo se ejecutará 2 veces y el segundo ciclo se ejecutará n veces. Total se ejecutará por 2n veces. Por lo tanto, O (2n), que será O (n).

Entonces, parece que te equivocaste en el Ejemplo 3. En general, tiene razón en que los bucles anidados serán O (n ^ 2), pero aquí el diablo está en los detalles.

Echa un vistazo al primer bucle:

para (i = n – 3; i <= n - 1; i ++)

¿Ves esa inicialización? Es n – 3. La condición es <= n - 1. Esto significa que el número de veces que se ejecuta este bucle no depende realmente de n. Siempre se ejecutará tres veces (n-3, n-2 y n-1). Entonces, la línea de impresión se ejecuta 3n veces, lo que nos da una gran O de O (n).

Todo su razonamiento es correcto, excepto el Ejemplo # 3. El bucle externo no itera n veces. Se itera exactamente 3 veces (independientemente del valor de n). Por lo tanto, el bucle interno, que es O (n), se ejecuta 3 veces. Llevándonos a O (3n) = O (n).

Me equivoqué ex3. Aunque fue O (n ^ 2). Debería haber tenido cuidado al contar el número de veces que se ejecuta el ciclo externo para el bucle. Me di cuenta de que se ejecuta 3 veces solo después de leer los comentarios.

Su impresión (ALGUNAS MULTIPLICACIONES) es su operación principal. Es 1. Esto se debe a que es la operación principal del algoritmo. Una buena manera de pensarlo es como la unidad en la que medimos. EG: “A medida que aumenta n, realizaremos multiplicaciones O (n)”.

Técnicamente, no es incorrecto llamar a una operación de multiplicación O (n), pero generalmente no usamos grandes o cuando consideramos las cosas a esas profundidades.

El ejemplo 3 es O (n) porque el bucle externo itera un número fijo de veces (3) y, por lo tanto, es O (1).