Сравнение алгоритма с О-нотацией

Question

Мы рассмотрим два алгоритма, Algo1 и Algo2, которые решают одно и то же проблема. Для любого ввода размером n Algo1 требуется время T_1(n) и Algo2 занимает время T_2(n).

Предположим, что T_1(n) завершается в O(n^2) и T_2(n) в O(n^3). Означает ли это, что существует n0 такой, что для n > n0* Algo1 работает быстрее, чем Algo2 на входах размера n?

Извините, я очень новичок в этой теме, и я не уверен, как начать даже подходить к этой проблеме. Любые намеки в правильном направлении будут чрезвычайно ценны! Спасибо!

Answer 1

В качестве контрпримера, вот два алгоритма для вычисления квадрата целого числа в JavaScript.

Algorithm1:

console.log( Algorithm1( 5 ) ); // 25

function Algorithm1 ( n ) {
  let count = 0;
  for ( let i = 0; i < n; i++ )
    for ( let j = 0; j < n; j++ )
      count++;
  return count;
}

Algorithm2:

console.log( Algorithm2( 5 ) ); // 25

function Algorithm2 ( n ) {
  return n*n;
}

Алгоритм1 находится в Ө(n²) и, следовательно, не в O(1).

Алгоритм2 находится в O(1) и, следовательно, тривиально также в O(n³).

Таким образом, нет n0 такого, что для n > n0 Алгоритм1 быстрее Алгоритма2.