Calculo complejidad de un algoritmo

[kasiko]

Hola,

A ver si alguien me puede decir como se hace esto:

Código [Seleccionar] Expandir

Calcular la complejidad en tiempo del algoritmo que calcula el conjunto (X)
de las partes de X (suponiendo que la unión de un elemento a una lista mediante
Append[lista, elemento] es una instrucción básica del ordenador).

X = {lista de elementos};
Partes = {{}};
For[j = 1, j <= Length[X], j++, temp = Length[Partes];
For[i = 1, i <= temp, i++, Partes = Append[Partes, Append[Partes[[i]], X[[j]]]]; ];
];
Print["El conjunto partes del conjunto X = ", X, " es el conjunto P(X) = ", Partes]

[[Case]]

Calcular la complejidad de un algoritmo es contar los pasos que necesita para terminar.
Si entiendo bien tu algoritmo lo que hace es calcular el conjunto potencia, que tiene una longitud de 2^n.
Por lo tanto para calcular ese arreglo o lista, su complejidad es  O(2^n).

[kasiko]

Lo primero, gracias por responder.

Lo segundo, ¿me podrías decir / explicar como has llegado a esa conclusion?
Es que es eso lo que no entiendo como hacer.

[[Case]]

Ese problema lo resolvi en algebra hace unos años, la verdad no me acuerdo de donde sale ese resultado.
Pero si te fijas en wikipedia te dice la formula.

http://es.wikipedia.org/wiki/Conjunto_potencia