Time Complexity of Loop with Powers - GeeksforGeeks

Time Complexity of Loop with Powers - GeeksforGeeks

What is the time complexity of below function?

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 of above function can be written as 1^k + 2^k + 3^k + … n1^k.

Let us try few examples:

k=1  Sum = 1 + 2 + 3 ... n       = n(n+1)/2       = n2 + 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       

In general, asymptotic value can be written as (n^k+1)/(k+1) + Θ(n^k)

Note that, in asymptotic notations like Θ we can always ignore lower order terms. So the time complexity is Θ(n^k+1 / (k+1))

Read full article from Time Complexity of Loop with Powers - GeeksforGeeks