What is the time complexity of the function?

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    

  }    

}

}

Answer 1

We need to calculate upper bound of this series summation.S =  $1^{k} + 2^{k} + 3^{k} + ------ + n^{k}$.

for k = 1 S = $\large \frac{n*(n+1)}{2} = O\left ( n^{2} \right )$ 

for k = 2 S = $\large \frac{n*(n+1)(2*n+1)}{6} = O\left ( n^{3} \right )$

for k = 3 S = $\large \left ( \frac{n*(n+1)}{2} \right )^{2} = O\left ( n^{4} \right )$

--------------------------------------------------------

In this question ans should be  = $\large O\left ( n^{k+1} \right )$

Answer 2

Here inner loop is running for p times which is equal to i^k.

So, Total time complexity for all i ( 1<=i <=n). will be,

T(n)= 1^k + 2^k + 3^k + 4^k + ...... + n^k     

      = (n+1)^k

      = O((n+1)^k) 

https://arxiv.org/pdf/1011.2154v1.pdf

Comments

Can you please describe the solution?