Cómo encontrar la notación Big O del siguiente programa

j comienza en 1 y se duplica en cada iteración.

el número de dobles que puede hacer hasta que exceda n es log2 (n).

puede calcular el número exacto de iteraciones, podría ser log2 (n) + 1, o tal vez log2 (n) -1 pero la complejidad del tiempo es log2 (n) independientemente de que los factores constantes no cambien la complejidad del tiempo.
En términos generales, todas las complejidades de registro se especifican como O (log (n)), independientemente de la base.

Ejecuciones de ejemplo:

n = 1
j = 1, (1 <1 es falso) hecho
entonces 0 iteración para n = 1.

n = 8
j = 1, (1 <8), j = 2, a ++
j = 1, (2 <8), j = 4, a ++
j = 1, (4 <8), j = 8, a ++
j = 1, (8 <8 es falso), hemos terminado.
3 iteraciones para n = 8

Big O se basa en la relación entre el número de iteraciones y el conjunto de datos de entrada. Dado que la variable de índice se duplica en cada iteración, el Big O de este algoritmo es log (N), porque el número total de iteraciones siempre es menor que N y en proporción logarítmica. (Es la duplicación de la variable de índice cada vez que eso es la señal).

Omry Yadan y Andrew Silverman explican por qué las iteraciones resultan ser O (log (n)). Lo único que tengo que agregar es que el código dentro de la iteración dada es O (1) (tiempo de ejecución “constante”) ya que la cantidad de trabajo cada vez que entras en ese ciclo no depende de n en absoluto. Analizar el tiempo de ejecución de un programa con más complicaciones dentro del ciclo principal (por ejemplo, casi cualquier implementación de tipo) tendrá que tener en cuenta el tiempo de ejecución del ciclo interno en el análisis O grande.

Supongamos que n = 20

Este bucle iterará 5 veces hasta que cumpla con la lógica de terminación.

Si calcula el logaritmo binario de n, encontrará [math] log_2 (n) [/ math] = 4.321928, que es casi 5
Entonces, a partir de la observación anterior, podemos decir que la complejidad de este código es O (log n)

Cada vez que se ejecuta el ciclo, el i se convierte en la mitad hasta que se convierte en cero. El valor de I se convierte en el piso de n, n / 2, n / 4, ………. hasta> 0 donde se detiene para que el ciclo se ejecute durante [math] \ lfloor log_2 n \ rfloor +1 [/ math] veces, que es [math] O (log n). [/ math]