I am learning about Big O Notation running times and amortized times. I understand the notion of *O(n)* linear time, meaning that the size of the input affects the growth of the algorithm proportionally…and the same goes for, for example, quadratic time *O(n ^{2})* etc..even algorithms, such as permutation generators, with

*O(n!)*times, that grow by factorials.

For example, the following function is *O(n)* because the algorithm grows in proportion to its input *n*:

```
f(int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d", i);
}
```

Similarly, if there was a nested loop, the time would be O(n^{2}).

But what exactly is *O(log n)*? For example, what does it mean to say that the height of a complete binary tree is *O(log n)*?

I do know (maybe not in great detail) what Logarithm is, in the sense that: log_{10} 100 = 2, but I cannot understand how to identify a function with a logarithmic time.