Algo doubt

Question

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

      }

    }

}

Time complexity= ?

Comments

assuming pow(i,k0 work in O(logk)

complexity = 1^k+2^k+------------+n^k + nlogk+n

---

time complexity is Θ(n^k+1 / (k+1))

Answer 1

1^k+2^k......................+n^k+nlogk<=n^k+n^k.................................+n^k=O(n^(k+1))