in Algorithms retagged by
274 views
0 votes
0 votes

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= ?

in Algorithms retagged by
274 views

2 Comments

assuming pow(i,k0 work in O(logk)

complexity = 1^k+2^k+------------+n^k + nlogk+n
0
0

time complexity is Θ(n^k+1 / (k+1))

0
0

1 Answer

0 votes
0 votes
1^k+2^k......................+n^k+nlogk<=n^k+n^k.................................+n^k=O(n^(k+1))

Related questions

1 vote
1 vote
1 answer
3
nikkey123 asked in Algorithms Jan 4, 2018
198 views
nikkey123 asked in Algorithms Jan 4, 2018
198 views