General Plan for Analyzing Recursive Algorithms:
The approach for recursive algorithms involves several systematic steps:
1 - Define Input Size: Establish the algorithm's input size, often the value of n itself.
2 - Identify Basic Operation: Determine the most frequently executed operation; in this example, it's the multiplication.
3 - Assess Variation on Input: Check if the number of operations varies based on input characteristics. If so, analyze for different cases (worst, average, best).
4 - Formulate Recurrence Relation: Set up a recurrence relation for the count of the basic operation, ensuring an appropriate initial condition is included
5 - Solve the Recurrence: Determine an explicit formula or the order of growth for the solution of the recurrence.