Skip to content
Related Articles

Related Articles

Time Complexity of Loop with Powers

View Discussion
Improve Article
Save Article
  • Difficulty Level : Medium
  • Last Updated : 30 Dec, 2021
View Discussion
Improve Article
Save Article

What is the time complexity of the below function?

C++




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
        }
    }
}
 
// This code is contributed by Shubham Singh

C




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

Java




static void fun(int n, int k)
{
    for (int i = 1; i <= n; i++)
    {
        int p = Math.pow(i, k);
        for (int j = 1; j <= p; j++)
        {
            // Some O(1) work
        }
    }
}
 
// This code is contributed by umadevi9616

Python3




def fun(n, k):
     
    for i in range(1, n + 1):
        p = pow(i, k)
        for j in range(1, p + 1):
            # Some O(1) work
         
 
# This code is contributed by Shubham Singh

C#




static void fun(int n, int k)
{
    for (int i = 1; i <= n; i++)
    {
        int p = Math.Pow(i, k);
        for (int j = 1; j <= p; j++)
        {
            // Some O(1) work
        }
    }
}
 
// This code is contributed by umadevi9616

Javascript




<script>
 
// JavaScript program for the above approach
function fun(n, k)
{
    for(let i = 1; i <= n; i++)
    {
        int p = Math.pow(i, k);
        for (let j = 1; j <= p; j++)
        {
            // Some O(1) work
        }
    }
}
 
// This code is contributed by Shubham Singh
 
</script>

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/2 + 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)
If  n>=k then the time complexity will be considered in O((nk+1)/(k+1)) and if n<k, then the time complexity will be considered as  in the O(nk)

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


My Personal Notes arrow_drop_up
Recommended Articles
Page :

Start Your Coding Journey Now!