Выполняют ли обе эти факториальные функции в O (n)?

Question

Рекурсивная функция определяется как так:

function factrec($x) { 
    if($x <= 1) { 
     return $x; 
    } else { 
     return $x * factrec($x - 1); 
    } 
} 

И итерационный здесь:

function factiter($x) { 
    $y = $x; 
    while($y > 1) { 
     $x *= ($y - 1); 
     $y--; 
    } 
    return $x; 
} 

Я прочитал, что на рекурсивной функции тело O (1) и рекурсивные вызовы O (n- 1) делает его O (n), но для итеративного это O (n) также?

Answer 1

Да, обе версии работают в O (n) времени. Обоснование итеративной версии в основном та же, что и для рекурсивной версии: тело цикла работает в O (1) раз и выполняется n раз.

Однако следует отметить, что итеративная версия работает в пространстве O (1), в то время как в рекурсивной версии используется пространство стека O (n) (поскольку имеется глубина рекурсии n).

Answer 2

Да, это O (n). Попытайтесь представить, сколько операций процессор будет работать, когда у вас есть большое значение x. При больших значениях он не становится более сложным, и он всегда является одной и той же операцией линейным способом.