How to measure the complexity of an algorithm?

Question

I need to know if my algorithm meets the demand of the following statement:

Implement an algorithm with O(n) complexity that performs the factorial of a number x such that x belongs to Naturals.

#include <stdio.h>
/* recebe um inteiro x;
 * retorna o fatorial de x.
*/
int fatorial (int x)
{   
if (x == 0)
    return 1;
return x * fatorial(x-1);
}
int main (void)
{
int n;
scanf("%d", &n);
printf("%d\n", fatorial(n));

return 0;
}

If possible explain to me how to make the measurement.

Answer 1

Measuring the complexity of an algorithm is traditionally done in computer science using asymptotic analysis which uses what is called notation Big O (o(n) of which its statement speaks).

An algorithm with complexity O(n) is nothing more than a time algorithm linear, which means that the time it takes to execute is a direct reflection of the size of the data input it uses and that this time grows steadily and linear...!

In practical terms what is desired by the enunciation of its problem is that if we say its algorithm performs a step that takes approximately 1 second to calculate the factor of 1 the calculation of the factor of 2 should perform two steps and take approximately 2 seconds, the factor of 3 would perform three steps and take approximately 3 seconds, and so on, for each value above your time grows linearly.

When your algorithm meets demand, yes it does, this can be confirmed by seeing that each factorial above a previous generates only an extra call to fatorial whereas fatorial performs only constant time operations (I won’t go into more detail here because the subject is extensive, I suggest you see the links I used on asymptotic analysis and Big O).

Answer 2

The complexity O(n) (linear) means that for each element of the collection that needs to manipulate, there must be at most one step in the algorithm.

You can determine the amount of steps by doing a table test, that is, mentally run the algorithm and go jotting down the state changes of the variables and sub-expressions, and go counting the steps to achieve the goal.

So for example, if you ask for the factorial of 5 you can run in up to 5 steps. For the factorial of 8, you can do it in up to 8 steps.

In this case "step" can be understood the call to function fatorial.

Another way is to activate the debug and go running and seeing how many steps have taken.

But the basic factor calculation is known as O(n) even complexity.

Answer 3

The complexity of algorithms can be measured in different ways, from intuitively to easy algorithms, for example, with iteration loops, but for algorithms involving recursion, the most recommended and formal method, which is to research the Master Theorem, which involves three types of notation.