О нотация, разбор определения

Нотация O(f) часто используется для описания скорости роста функций в виде O(N)(O(N*N), O(log(N)) и т.д. и т.п.). Фактически, это означает, что некоторая g(N) возрастает не быстрее, чем линейная (квадратичная, логарифмическая, ... ) функция от N с некоторыми коэффициентами.

Например, функция g(N) = 4*N имеет порядок O(N), т.к. мы можем записать соотношение g(N) < 10*N и это соотношение будет справедливым для любых N > 1. В этом примере c0 = 10, а N0 = 1.

А вот еще один пример, для более сложной функции g. Пусть g(N) = 2*N*N + N. Эта функция имеет порядок O(N*N), поскольку для любого N > 1 справедливо g(N) < 4*N*N. В этом примере c0 = 4, а N0 = 1.

На самом деле, параметры c0 и N0 могут быть произвольными, но должны быть конечными и не зависеть от N.

Сама нотация, полезна при описании сложности алгоритмов. В этом случае она показывает как растет число действий, выполняемых алгоритмом от количества входных данных. При этом, точное количество итераций, обычно, не столь существенно. Важно лишь некоторое оценочное значение.

Например, если есть две функции (алгоритма) сортировки массивов, одна из которых имеет порядок O(N), а другая O(N*N), то первая функция эффективнее чем вторая.

Ответ верный. Приведу только пример, который, имхо, сделает его чуть понятней. Пусть g(N) = N*N + log(N) Тогда порядок g(N) будет O(N*N) т.к. при N0 = 1 и C0 = 2 для любого N>N0 g(N) < C0 * N*N истинно.

Просто во всех ранее приводимых примерах f(N) == g(N), что, видимо, немного сбивает с толку.