Complejidad temporal del bucle con potencias

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

void fun(int n, int k)
{
    for (int i = 1; i <= n; i++)
    {
        int p = pow(i, k);
        for (int j = 1; j <= p; j++)
        {
            // Some O(1) work
        }
    }
}
 
// This code is contributed by Shubham Singh

void fun(int n, int k)
{
    for (int i = 1; i <= n; i++)
    {
        int p = pow(i, k);
        for (int j = 1; j <= p; j++)
        {
            // Some O(1) work
        }
    }
}

static void fun(int n, int k)
{
    for (int i = 1; i <= n; i++)
    {
        int p = Math.pow(i, k);
        for (int j = 1; j <= p; j++)
        {
            // Some O(1) work
        }
    }
}
 
// This code is contributed by umadevi9616

def fun(n, k):
     
    for i in range(1, n + 1):
        p = pow(i, k)
        for j in range(1, p + 1):
            # Some O(1) work
         
 
# This code is contributed by Shubham Singh

static void fun(int n, int k)
{
    for (int i = 1; i <= n; i++)
    {
        int p = Math.Pow(i, k);
        for (int j = 1; j <= p; j++)
        {
            // Some O(1) work
        }
    }
}
 
// This code is contributed by umadevi9616

<script>
 
// JavaScript program for the above approach
function fun(n, k)
{
    for(let i = 1; i <= n; i++)
    {
        int p = Math.pow(i, k);
        for (let j = 1; j <= p; j++)
        {
            // Some O(1) work
        }
    }
}
 
// This code is contributed by Shubham Singh
 
</script>

La complejidad temporal de la función anterior se puede escribir como 1 ^k + 2 ^k + 3 ^k + … n1 ^k .

Probemos algunos ejemplos: 

k=1
Sum = 1 + 2 + 3 ... n 
    = n(n+1)/2 
    = n2/2 + n/2

k=2
Sum = 12 + 22 + 32 + ... n12.
    = n(n+1)(2n+1)/6
    = n3/3 + n2/2 + n/6

k=3
Sum = 13 + 23 + 33 + ... n13.
    = n2(n+1)2/4
    = n4/4 + n3/2 + n2/4     

En general, el valor asintótico se puede escribir como (n ^k+1 )/(k+1) + Θ(n ^k )
Si n>=k entonces la complejidad del tiempo se considerará en O((n ^k+1 )/( k+1)) y si n<k, entonces la complejidad temporal se considerará como en O( n ^k )

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.