Member Avatar for corby

Here some psuedocode for an algorithm:

function Fact(n)
if n <=1 then
return(1)
else
return (n * Fact(n-1)!
end-if
end-fact

Now how do i find the recurrence equation for the program? Any help or hint would be appreciated!

  • 2 Contributors
  • 1 Reply
  • 87 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by galagatron
Member Avatar for galagatron

Since your recursion doesn't create a recursion tree (there's always only 1 subproblem, and it's the same size as every other subproblem), and since the program recurses n-1 times, a simple recurrent equation, i.e., running time description, would be:

T(n)= BIG_THETA(n-1)


Assuming that by "(n * Fact(n-1)!" you meant "(n * Fact(n-1))". If not, then I don't understand your syntax.

Edited by galagatron because: .
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.