Time Complexity of Loop with Powers

What is the Time Complexity of Loop with Powers with below function?

[ad type=”banner”] [pastacode lang=”c” manual=”void%20fun(int%20n%2C%20int%20k)%0A%7B%0A%20%20%20%20for%20(int%20i%3D1%3B%20i%3C%3Dn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20int%20p%20%3D%20pow(i%2C%20k)%3B%20%0A%20%20%20%20%20%20for%20(int%20j%3D1%3B%20j%3C%3Dp%3B%20j%2B%2B)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%2F%2F%20Some%20O(1)%20work%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D” message=”” highlight=”” provider=”manual”/]

Time complexity of above function can be written as 1^k + 2^k + 3^k + … n1^k.

Let us try few examples:

[ad type=”banner”] [pastacode lang=”c” manual=”k%3D1%0ASum%20%3D%201%20%2B%202%20%2B%203%20…%20n%20%0A%20%20%20%20%3D%20n(n%2B1)%2F2%20%0A%20%20%20%20%3D%20n2%20%2B%20n%2F2%0A%0Ak%3D2%0ASum%20%3D%2012%20%2B%2022%20%2B%2032%20%2B%20…%20n12.%0A%20%20%20%20%3D%20n(n%2B1)(2n%2B1)%2F6%0A%20%20%20%20%3D%20n3%2F3%20%2B%20n2%2F2%20%2B%20n%2F6%0A%0Ak%3D3%0ASum%20%3D%2013%20%2B%2023%20%2B%2033%20%2B%20…%20n13.%0A%20%20%20%20%3D%20n2(n%2B1)2%2F4%0A%20%20%20%20%3D%20n4%2F4%20%2B%20n3%2F2%20%2B%20n2%2F4%20%20%20″ message=”” highlight=”” provider=”manual”/]

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))