f(n) = O(g(n)) means c·g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c·g(n), for large enough n.

Binary search is a good example of an O(log n) algorithm. To locate a particular element e in a sorted set containing n elements, you start by comparing e against the middle, or (n/2)nd element. Regardless of whether e belongs before this middle element or after it, after only one comparison you can discard one half of all the elements in the set. The number of steps the algorithm takes equals the number of times we can halve n until only one element is left. By definition, this is exactly log2 n.

void selection_sort(int s[], int n) {
    int i,j; /* counters */
    int min; /* index of minimum */
    for (i=0; i<n; i++) {
        min=i;
        for (j=i+1; j<n; j++)
            if (s[j] < s[min]) min=j;
        swap(&s[i],&s[min]);
    }
}

S(n) = (n - 1) + (n - 2) + … + 2 + 1 < n(n - 1)/2 = O(n2)