Асимптотический анализ алгоритмов

Полезная статья: "Асимптотический анализ алгоритмов".

Во многих работах описывающих те или иные алгоритмы, часто можно встретить обозначения типа: 

O(g(n)), Ω(g(n)), Θ(g(n)).

Давайте разбермся, что же это такое, но сначала я перечислю основные классы сложности применяемые при анализе:

f(n) = O(1) константа
f(n) = O(log(n)) логарифмический рост
f(n) = O(n) линейный рост
f(n) = O(n*log(n)) квазилинейный рост
f(n) = O(n^m) полиномиальный рост
f(n) = O(2^n) экспоненциальный рост

Если раньше вы не встречались с подобными обозначениями, не переживайте, после прочтения этой статьи, все станет намного понятнее.