Que signifie exactement O(log n) ?

Je suis en train d'apprendre les temps d'exécution et les temps amortis de la Notation Big O. Je comprends la notion de temps linéaire O(n), ce qui signifie que la taille de l'entrée affecte la croissance de l'algorithme de manière proportionnelle... et il en va de même pour, par exemple, le temps quadratique O(n2) etc... même les algorithmes, tels que les générateurs de permutation, avec des temps O(n !), qui croissent par factorielles.

Par exemple, la fonction suivante est O(n) car l'algorithme croît proportionnellement à son entrée n :

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

De même, s'il y avait une boucle imbriquée, le temps serait O(n2).

Mais qu'est-ce que O(log n) exactement ? Par exemple, qu'est-ce que cela signifie de dire que la hauteur d'un arbre binaire complet est O(log n) ?

Je sais (peut-être pas en détail) ce qu'est le logarithme, dans le sens où : log10 100 = 2, mais je n'arrive pas à comprendre comment identifier une fonction avec un temps logarithmique.