Big-Oh de bucles anidados, donde el bucle interno depende de i * n e i * i del bucle externo - big-o, bucles anidados

¿Cuál es el Big-Oh de los siguientes bucles anidados:

sum=0;
for(i=0;i<n;i++)
for(j=0;j<i*n;j++)
sum+=i;

y

sum=0;
for(i=0;i<n;i++)
for(j=0;j<i*i;j++)
sum+=i;

Creo que es O (n ^ 2), pero todo lo que he vistoLos dos circuitos se encuentran utilizando n como prueba, por lo que no sé si O (n ^ 2) es correcto. Si alguien pudiera verificar mi comprensión o explicar por qué estoy equivocado, lo apreciaría. ¡Gracias!

Respuestas

Yo diría que ambos son O(n^3), ya que en ambos casos el bucle interior es O(n^2) y el bucle exterior es O(n). Por supuesto que correrán mucho menos que n ^ 3veces, pero si representas gráficamente el tiempo de ejecución como una función de n, cuando n se hace enorme, verás que la forma se parece más a una forma cúbica que a una cuadrática. Mi prueba es que si desenrolla la suma del primero, obtendrá:

ya que tienes n términos, cada uno de los cuales es O(n^2), todo el asunto es O(n^3), aunque sea muy pequeño O(n^3).

Para el segundo:

que es incluso más pequeño que el primero, pero aún así O(n^3).