what is the time complexity ?

Question

sum=0;
for(i=0;i<n;i++)
    for(j=0;j<i*i;j++)
        for(k=0;k<j;k++)
            sum++;

Comments

Its $O(n^5)$.

In worst case $i$ goes from $0$ to $n$, j goes from $0$ to $n^2$ and k goes from $0$ to $n^2$ .

So, Time Complexity : $O(n)*O(n^2)*O(n^2) = O(n^5)$

Detailed mathematical proof can be done simply summation of values of $j$ for each value of $i$. and then considering the values of k.

T(n) = $((n)*(n+1)*(2*n+1)/6)$$*$$O(n^2)$

Answer 1

See first loop will run O(n) time

Middle loop condition j<i*i so it will run O(n² ) time (since i is running n time)

Last loop condition k<j so i will run O( n² ) time (j is running n² time)

So total time complexity=O(n⁵)

Comments

int fun(int n){
  int count = 0;
  for (int i = n; i > 0; i /= 2)
    for (int j = 0; j < i; j++)
      count += 1;
  return count;
}

then this function should give O(nlogn).

since outer loop run O(logn) time

inner loop O(n) time 

---

@Khushboo : For your code,

According to my calculation it is giving total complexity O(n)

For first iteration, i=n : inner loop will run n times

For second iteration i=n/2 : inner loop will run n/2 times

...

Total iterations will be log(n) as i will keep on decreasing by factor of 2.

Now, total number of times inner loop runs :

= n + n/2 + n/4 + n/8 and so on up to log(n) terms.

= n * [sum of log(n) terms of a GP having a=1 and r=1/2]

= n * [2 (n-1)/n]

= 2(n-1)

=O(n)

 

Please correct me if I am wrong !!!

---

So if I put count++ before the third loop, it should print a value $O(n^2)$ when the loop ends?

---

It will print O(n^3) then.

Answer 2

The run time can be mentioned mathematically as,

$T(n) = \sum_{i=0}^{n-1}\sum_{j=0}^{i^2-1}\sum_{k=0}^{j-1}c$

i.e

$T(n) =c \sum_{i=0}^{n-1}\sum_{j=0}^{i^2-1}j$

$T(n) =c \sum_{i=0}^{n-1}\frac{(i^2-1)(i^2)}{2}$

$T(n) =c \sum_{i=0}^{n-1}(i^4 - i^2)$

considering the higher order term

$T(n) =O(c \sum_{i=0}^{n-1}(i^4) )$

$T(n) =O(n^5)$

Comments

Can you provide the general term for the final value of the variable 'sum' after completion o this code snippet?

---

That will be the solution to the above equation (before being approximated) with c = 1.