some examples of algorithm complexity of nested loops? -

i have seen in cases complexity of nested loops o(n^2), wondering in cases can have following complexities of nested loops:

• o(n)
• o(log n) have seen somewhere case this, not recall exact example.

i mean there kind of formulae or trick calculate complexity of nested loops? when apply summation formulas not right answer.

some examples great, thanks.

here example time complexity o(n), have double loop:

int cnt = 0; (int = n; > 0; /= 2) {     (int j = 0; j < i; j++) {         cnt += 1;     } } 

you can prove complexity in following way:

the first iteration, j loop runs n times. second iteration, j loop runs n / 2 times. i-th iteration, j loop runs n / 2^i times. in total: n * ( 1 + 1/2 + 1/4 + 1/8 + … ) < 2 * n = o(n)

---

it tempting runs in o(log(n)):

int cnt = 0; (int = 1; < n; *= 2) {     (int j = 1; j < i; j*= 2) {         cnt += 1;     } } 

but believe runs in o(log^2(n)) polylogarithmic