Análisis asintotico

Ahora demostrare un ejemplo del ejercicio 2 del examen: Análisis asintotico. Esta fue la forma como respondí a la pregunta 2 del examen anterior.

2. Encuentre una función de complejidad asintotica f(n) así que la función g(n) definida experimentalmente por doce puntos en la siguiente tabla sea $\Omega f(n)$.

Justifique esto con una gráfica y discute la calidad de la cota obtenida.

n	g(n)	n	g(n)	n	g(n)
3	15	130	3,800	3,982	190,000
12	170	203	7,500	5,002	240,000
30	600	603	22,000	10,393	550,000
57	1,500	1,038	42,000	40,039	2,600,000

Primero noto que con los primeros 4 datos, f(n) podría ser n² porque 3² se aproxima a 15, 12² se aproxima 170, 30² se aproxima a 600 y 57² se aproxima a 1,500 pero al calcular los últimos, no:

3,982²= 15,856,324
5,002²= 25,020,004
10,393²= 108,014,449
40,039²= 1,603,121,251

Como la complejidad asintotica es mas importante a grandes instancias y n² crece demasiado rápido, probaremos con una función inferior pero que obviamente sea superior a n.

3,982^1.5= 251,276.5054
5,002^1.5= 353,765.5438
10,393^1.5= 1,059,525.4449
40,039^1.5= 8,011,702.8514

Demasiado, ahora con potencia 1.4:

3,982^1.4= 109,683.6155
5,002^1.4= 150,938.8936
10,393^1.4= 420,181.8590
40,039^1.4= 2,776,364.6813

Suficiente para mi, g(n)= n^1.4, ahora busquemos una cota inferior.

Sabemos que una cota inferior a g(n) puede ser f(n)= log n, pero no esta tan próxima a n^1.4, una mas inmediata seria n^1.35, así que la tomaremos y comparamos:

3,982^1.35= 72,466.4013
5,002^1.35= 98,592.5224
10,393^1.35= 264,606.3437
40,039^1.35= 1,634,377.4061

Los datos son inferiores a los de n^1.4, entonces f(n)= n^1.35 sera nuestra cota inferior u $\Omega f(n)$.

Vemos la gráfica:

Como pueden ver la linea roja representa nuestra función g(n) aproximada, la verde la cota inferior f(n) y la azul los datos experimentales de la tabla. La cota inferior resulto bastante buena ya que no nos fuimos hasta log n para hacerla inferior a la lineal n^1.4 sino a n^1.35 que se encuentra inmediatamente debajo de g(n).


Por ultimo me gustaría comentar sobre como realice esta entrada porque a alguien le podría servir en un futuro. Las potencias que se ven por el estilo de n^e, se realizan con una herramienta que ya viene incluida en los blogs que se llama superscript y subscript y se hacen escribiendo <sup> </sup> y <sub> </sub> respectivamente, mientras que los símbolos como $\Omega$ se hacen agregando al blog un gadget (código en java) para que reconozca escritura LaTeX, pero eso ya lo explique en esta entrada.

Por otro lado la gráfica la hice con un programa llamado gnuplot de descarga y uso gratuito, cuando lo descargue me incluyo un documento tutorial o guía para aprender a usarlo. Es un programa a base de linea de comando pero es muy potente.