# algorithm – Big O Notation for a For-Loop

## algorithm – Big O Notation for a For-Loop

A loop like this:

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

iterates *n* times, so if `doSomething`

has O(1) running time, then the loop as a whole has O(*n*) running time.

Similarly, a loop like this:

```
for (int j = 0; pow(j, 2) < n; j++) {
doSomething(j);
}
```

iterates ⌈√*n*⌉ times, so if `doSomething`

has O(1) running time, then the loop as a whole has O(√*n*) running time.

By the way, note that although `pow(j, 2)`

is O(1) running time — so it doesnt affect your loops asymptotic complexity — its nonetheless pretty slow, because it involves logarithms and exponentiation. For most purposes, Id recommend this instead:

```
for (int j = 0; j * j < n; j++) {
doSomething(j);
}
```

or perhaps this:

```
for (int j = 0; 1.0 * j * j < n; j++) {
doSomething(j);
}
```