0

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) and the recursive calls O(n-1) making it O(n), but for the iterative is it O(n) as well?

John
  • 1,110
  • 3
  • 14
  • 28
  • 1
    `function factorial($x) { for ($y = $x; $y-- > 1; $x *= $y); return $x; }`: PHP's so nice. (Hope I didn't make a fault :D) – NikiC Sep 26 '10 at 12:06

2 Answers2

8

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).

sepp2k
  • 363,768
  • 54
  • 674
  • 675
  • This is perfect for my answer actually, I just needed to know why on my benchmark that recursive was THAT much slower than the other. I'll put that in my notes. – John Sep 26 '10 at 10:34
  • One can refactor the recursive approach to allow tail call and thus also be O(1) in space. But it does make it less clear. – Richard Sep 26 '10 at 10:54
  • `gcc -O2` turns a recursive factorial into iteration (see http://stackoverflow.com/questions/405770/why-are-compilers-so-stupid/414774#414774). I wouldn't be too surprised if GHC did something similar in simple cases. Yet again, programmers underestimate compiler writers ;) But yeah, PHP won't optimize it. –  Sep 26 '10 at 11:16
0

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.

Benoit
  • 76,634
  • 23
  • 210
  • 236
  • 1
    actually as for the processor this is not `O(n)` because multiplication is not `O(1)` operation. But if you think of multiplication as `O(1)` it is `O(n)` – Itay Karo Sep 26 '10 at 10:26
  • I'm glad my thoughts were right. I was bored benchmarking the two, the recursive function skyrockets above iterative when calculating higher factorials.. just was wondering if they were both O(n) regardless of that result. Then again I'm being stupid and using PHP to do this.. maybe that is why it's much higher. – John Sep 26 '10 at 10:28
  • 1
    Multiplication on primitive data types is O(1). As long as it's smaller than a 64-bit integer, it'll be O(1). But yes, if it's an arbitrary precision integer type, then you're right. But both algorithms multiply. That won't set them apart. Creating the stack frame for each successive call in the recursive version will surely slow it down. – JoshD Sep 26 '10 at 10:28
  • sorry, I was assuming $x and $y to have an int data type. Factorial function is usually computed on integers. Otherwise you need the Gamma function. – Benoit Sep 26 '10 at 10:30