Докажите, что различные определения big-Oh с n> = 1 или n> N эквивалентны

Question

Я сталкиваюсь с двумя немного разными определениями big-oh и должен доказать, что они эквивалентны друг другу:

Определение 1: f (n) = O (g (n)), если существуют такие константы c и N, что f (n) ≤ c g (n) для всех n> N.

Определение 2: f (n) = O (g (n)), если существует постоянная c такая, что f (n) ≤ c g (n) для всех n≥1.

Интуитивно я знаю, что если мы выберем c достаточно большим, мы сможем избавиться от N, как в определении 2. Но как доказать это, если определение 1 подразумевает определение 2, и наоборот.

Answer 1

Позвольте мне лучше объяснить мой комментарий к ответу @ btilly.

Когда g(n)>0 для всех значений n, оба определения фактически эквивалентны. Вот почему:

Во-первых, всегда верно, что когда выполняется определение 2, определение 1 также выполняется. На самом деле, мы можем выбрать N=0 в этом случае.

Предположим теперь, что определение 1 выполнено для некоторой константы c и некоторого числа N. Если N=0, у нас есть Определение 2. Если N>0, рассмотрим следующее количество:

c1 := max{f(1)/g(1), ..., f(N)/g(N)}

коэффициенты имеют смысл, потому что мы находимся в случае, когда g(n) всегда положительно. Кроме того, с

f(n)/g(n) <= c1        (1<=n<=N)

получаем

f(n) <= c1*g(n)        (1<=n<=N)

и поскольку f(n) <= c*g(n) для n>N, бывает, что

f(n) <= max(c1,c)*g(n)     for all n

как требует определение 2.

Answer 2

Они на самом деле не эквивалентны, и (1) является правильным определением.

Примером различия является то, что согласно (1), n = O(n log(n)), но по определению (2) это не может быть потому, что при n=1, потому что для любого c, c g(n) = c*1*log(1) = 0 < 1.

Причина, по которой (1) является правильным определением, заключается в том, что цель big-O состоит в том, чтобы отразить поведение "около бесконечности", и поэтому следует игнорировать конечное число особых случаев для малых n.

Причина, по которой вы увидите (2), состоит в том, что этого достаточно, чтобы установить big-O. Это просто не нужно.