если функция принимает два массива и эта функция будет повторять каждый массив один раз в O (n)

Question

Если функция принимает два массива и эта функция будет повторять каждый массив один раз в O (n)

a = [2 elements] // can be any length
b = [1000000 elements] // can be any length

function(a,b){
// NOT nested
  loop a  // O(n)
  loop b // O(n)
}

Это O(n+n), но мы упрощаем до O(n)?

Answer 1

Классы сложности времени - представление того, как время растет, когда n приближается к бесконечности. Таким образом, вы можете умножить их на любую конечную постоянную k, и временная сложность останется неизменной (потому что в конечном итоге это не будет иметь значения для невероятно больших значений n)

Взгляните сюда: https://en.wikipedia.org/wiki/Big_O_notation Вы можете увидеть соответствующий раздел в разделе «Умножение на константу»