What is the Time Complexity of Loop with Powers with below function?
Time complexity of above function can be written as 1k + 2k + 3k + … n1k.
Let us try few examples:
In general, asymptotic value can be written as (nk+1)/(k+1) + Θ(nk)
Note that, in asymptotic notations like Θ we can always ignore lower order terms. So the time complexity is Θ(nk+1 / (k+1))