time-complexity - sucesion - serie telescopica

Encontrando Big O de la serie armónica

Question

Pruebalo

1 + 1/2 + 1/3 + ... + 1/n is O(log n).
Assume n = 2^k

Puse la serie en el resumen, pero no tengo idea de cómo abordar este problema. Cualquier ayuda es apreciada

Answer 1

Aquí hay una formulación usando Matemáticas Discretas:

Entonces, H (n) = O (log n)

Answer 2

Esto se desprende fácilmente de un hecho simple en Cálculo:

Y tenemos la siguiente desigualdad:

Aquí podemos concluir que S = 1 + 1/2 + ... + 1 / n es (log (n)) y O (log (n)), por lo tanto es Ɵ (log (n)), el atado es en realidad apretado.

Answer 3

Pregunta
1 + 1/2 + 1/3 + ... + 1 / n
Supongamos que n = 2 ^ k

• Si el 3rd término es 1/3 y no 1/4 (1/2^2) , significa que hay n términos en todos, por lo que será O (n) . Es cierto que su suma puede ser log n , pero la complejidad es el número de iteraciones y no la suma de series.

• Considera resolverlo programáticamente. Terminarías ejecutando el bucle 1 a n veces y agregando 1 / n a la suma. ¿Cuántas veces se ejecutó? 1 to n O (n)

• Si el problema se cambió a 1 + 1/2 + 1/4 + ... + 1/n , la serie ahora se puede escribir como 1 + 1/2 + 1/4 + ... + 1/n ^ 2 + .. . + 1/2 ^ (k). Ahora la pista proporcionada por tu profesor también tiene sentido. ¿Cuántas veces se ejecutará el bucle? 0 to k = k + 1 times , y de ambas series podemos ver 2^k = n tanto k = log (n) . Entonces, la cantidad de veces que se ejecutó = log(n) + 1 = O(log n)

• Supongo que usted o su profesor hicieron un error tipográfico.

Actualizar

Como señaló Dukeling, por supuesto, asumo que the provided function is pseudo-code and calculating the time complexity of that . Ahora, después de un año, entiendo por qué obtuve votos mixtos para esta respuesta en particular. Chicos, esto es y está destinado principalmente para la codificación. Si tiene problemas no relacionados directamente con la programación, debe usar un sitio de stackexchange diferente, como https://math.stackexchange.com/