Wsrtjtyk

I'm trying to solve the complexity of this loop

for(int i= 0; i < n; i++) {    

 c = i;    

 while(c > 1){     

  O(1);     

  c = c / 2;     

 }    

}

as the while condition changes in every loop I don't know how to calculate that strange series.

I mean, if the loop where

for(int i= 0; i < n; i++) {     

 c = n;     

 while(c > 1){     

  O(1);     

  c = c / 2;     

 }

}

I know the while has a complexity of O(logn) and it repeats itself n times, so the complexity would be O(nlogn).

The problem I have with previous loop is "c=i". As c=i, first time (c=0) the loop would reproduce 0 times, when c=1 it would reproduce 0 times again, when c=2 it would reproduce 1 time, then the series would follow and it is 0, 0, 1, 2, 2, 3, 3... (while reproductions each time of for loop)

O(logn) would not repeat itself n times, would repeat a number of times I can't come up with, so I don't know how to solve it.

This need a bit of math involved.Given that log is well defined for a and b:

log(a) + log(b) = log(ab)

Here you have

log(1) + log(2) +....+ log(n) = log(1*....*n) = log(n!)

There is a mathematical approximation for log(n!), namely

 log(n!) ~ nlog(n) - n + 1

which reveal O(log(n!)= O(nlog(n))