Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Guías prácticas/Complejidad computacional/Solución al ejercicio 4 de complejidad computacional

1.

$k=0,005{\frac {ms}{elemento}}$

$0,005{\frac {ms}{elemento}}*x=1000ms$

$x=200000elementos$

2.

$k=0,0010857{\frac {ms}{elemento}}$

$0,0010857{\frac {ms}{elemento}}*xlnx=1000ms$

$xlnx=921060,5$

Con el método de punto fijo se puede aproximar la raíz:

$i$	$x_{i}$	$x_{i+1}={\frac {92106,5}{lnx_{i}}}$
0	4	664404,708
1	664404,708	68701,7804
2	68701,7804	82698,8091
3	82698,8091	81344,4948
4	81344,4948	81463,2911
5	81463,2911	81452,7778
6	81452,7778	81453,7075
7	81453,7075	81453,6253
8	81453,6253	81453,6325
9	81453,6325	81453,6319
10	81453,6319	81453,632
11	81453,632	81453,6319
12	81453,6319	81453,6319

$x\approx 81453elementos$

3.

$k=0,00005{\frac {ms}{elemento}}$

$0,00005{\frac {ms}{elemento}}*x^{2}=1000ms$

$x={\sqrt {20000000}}\approx 4472elementos$

4.

$k=0,0000005{\frac {ms}{elemento}}$

$0,0000005{\frac {ms}{elemento}}*x^{3}=1000ms$

$x={\sqrt[{3}]{2000000000}}\approx 1259elementos$

En todos los ejercicios anteriores se consideró el tiempo durante un segundo, cuando en realidad el enunciado hablaba sobre la cantidad de datos procesados en un minuto, hay que multiplicar todos los resultados por 60;