Analysis of Algorithm

Time Complexity of Loop with Powers

Time Complexity of Loop with Powers
Time Complexity of Loop with Powers- Analysis of Algorithm What is the time complexity of below function?Time complexity of above function can be written as

What is the Time Complexity of Loop with Powers with 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 1k + 2k + 3k + … n1k.

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

READ  Shortest Path-Some interesting shortest path questions

About the author

Venkatesan Prabu

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

Add Comment

Click here to post a comment

X