Почему алгоритм работающий за O(n) не всегда быстрее второго за O(n^2)?

• 1 - При достаточно маленьких n второй будет работать быстрее - при достаточно маленьком n разница между O(n) и O(n^2) будет минимальна и ничего определённого сказать нельзя про то, какой алгоритм будет работать быстрее
• 2 - Первый всегда быстрее второго - вот как-раз не всегда, а см. выше
• 3 - Второй всегда быстрее первого - нет, конечно
• 4 - При достаточно больших n первый будет работать быстрее - а вот это вполне похоже на суть разницы O(n) и O(n^2)

Можем подойти с точки зрения чистой теории, формально, без привлечения новых сущностей - n <= n^2:

1 - "При достаточно маленьких n второй будет работать быстрее" - очевидно нет, т.к. у нас нет никакой информации о каких-либо иных компонентах дающих вклад в скорость выполнения, кроме сложности.
2 - "Первый всегда быстрее второго" - нет, Т.к. при n=1 оба будут одинаковыми.
3 - "Второй всегда быстрее первого" - очевидно нет.
4 - "При достаточно больших n первый будет работать быстрее" - очевидно да.

Для начала покажу почему вы неправы про

Первый всегда быстрее второго

Пускай зависимость количества шагов первого алгоритма от размера входных данных выражается формулой f(n)=3*n, а для второго - g(n)=n^2.

Обратите внимание, что для всех n<3 f(n) > g(n), это видно хотя бы из графиков:

т.е. второй алгоритм будет делать меньше шагов, а значит работать быстрее, когда данных мало (n<3). При этом сложность первого алгоритма O(n), а второго O(n^2). Это контрпример, который показывает почему неверно утверждение, что алгоритм со сложностью O(n) всегда быстрее алгоритма со сложностью O(n^2).

Вероятно, нужно пояснить, что означает, что алгоритм имеет сложность O(n) или O(n^2) ну и в общем случае O(f(n)), где f(n) - некая функция.

Общее определение такое:

Алгоритм имеет сложность O(f(n)), если существуют такие числа C и N, что для количества шагов алгоритма (определяемое формулой g(n)) выполняется условие, что для каждого n>N: g(n) <= C*f(n)

Начну с примера для первого алгоритма, у которого количество шагов определяется по формуле k(n)=3*n. Если мы возьмем C=3 и N=1, то получаем, что для любого n>1 выполняется 3*n <= 3*n, а значит по определению алгоритм имеет сложность O(n). Тут f(n)=n и g(n)=3*n.