Do both these factorial functions run in O(n)?

The recursive function defined as so:

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

And iterative here:

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

I had read that on the recursive function the body is O(1) a开发者_Go百科nd the recursive calls O(n-1) making it O(n), but for the iterative is it O(n) as well?

Yes, both versions run in O(n) time. The reasoning for the iterative version is basically the same as for the recursive version: The body of the loop runs in O(1) time and is executed n times.

However it should be noted that the iterative version runs in O(1) space, while the recursive version uses O(n) stack space (because there's a recursion depth of n).

yes it is O(n). Try to imagine how many operations the processor will run when you have a large value of x. With large values, it does not get more complex, and it is always the same operation in a linear way.