Reglas para calcular la complejidad de un algoritmo

1. Sentencia sencilla:
Se refiere a las sentencias de asignacion de entrada y salida de datos, siempre y cuando no se trate de variables estructuradas cuyo tamaño esta relacionado con n. Requiere un tiempo constante de ejecucion siendo su complejidad O(1).

2. Secuencia de sentencias:
La complejidad de una serie de instrucciones de un programa sea delorden de la suma de las complejidades individuales dependiendo de las intrucciones que se traten.

3.Decision (if, switch):
La condicion if suele ser de complejidad constante sumando la peor rama posible ya sea en el then o en el else, la desicion multiple o switch tomara la peor de las ramas en todos los casos.

4. Bucles (ciclos):
En los bucles con contador explicito como el for se tienen dos casos que el tamaño de N forme parte del limite del ciclo o no.

a) N forma parte limite ciclo
for (int i=0; i N * O(1) = 0(n) complejidad Lineal

b) N no forma parte del limite del ciclo
for (int i=0l; i K*O(1) = O(1) Complejidad Constante

5. Llamadas a procedimientos.
La complejidad de llamar a un procedimiento esta dado por la complejidad de las instrucciones del procedimiento en si, pudiendo complicarse notablemente si se trata de procedimientos recursivos.

Funcione factorial No recursiva

int factorial(int n) O(n1)
{
int fact=1;
for(int i=n;i>0;i--)
{
fact*=i;
}
return fact;
}

=>complejidad lineal O(n)