Что именно означает O (log n)?

в настоящее время я изучаю время работы Big O Notation и амортизированное время. Я понимаю понятие O (n) линейное время, что означает, что размер входного сигнала влияет на рост алгоритма пропорционально...и то же самое касается, например, квадратичного времени O (n²) etc..даже алгоритмы, такие как генераторы перестановок, с O (n!) раз, которые растут на факториалы.

например, следующая функция это O (n) потому что алгоритм растет пропорционально его входу n:

f(int n) {

  int i;

  for (i = 0; i < n; ++i)

    printf("%d", i);

}

аналогично, если бы был вложенный цикл, время было бы O (n²).

но что же такое O (log n)? Например, что значит сказать, что высота полного двоичного дерева O (log n)?

Я знаю (может быть, не очень подробно), Что такое логарифм, в том смысле, что: log₁₀ 100 = 2, но я не могу понять, как идентифицировать функцию с логарифмическим временем.