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 = n^{2}+ n/2 k=2 Sum = 1^{2}+ 2^{2}+ 3^{2}+ ... n1^{2}. = n(n+1)(2n+1)/6 = n^{3}/3 + n^{2}/2 + n/6 k=3 Sum = 1^{3}+ 2^{3}+ 3^{3}+ ... n1^{3}. = n^{2}(n+1)^{2}/4 = n^{4}/4 + n^{3}/2 + n^{2}/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))**

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

## leave a comment

## 0 Comments