Complejidad para el cálculo de:

i=N
∑	i !  =  Ο(n2)
i=1

 Ecuación temporal = 2+( 2(N( N + 1 ) ) ) + 7N

N =

Complejidad del método de clasificación por   Selección. Ο(n²)

 Ecuación temporal = 6( N(N - 1) - (N / 2)(N - 1) ) + 15(N - 1) + 3

N =

Complejidad del método de clasificación por   Burbuja. Ο(n²)

 Ecuación temporal peor caso 12( N(N - 1) - (N / 2)(N - 1) ) + 6(N - 1) +3

 Ecuación temporal mejor caso 5 ( N(N - 1) - (N / 2)(N - 1) ) + 6(N - 1) +3

 Ecuación temporal caso medio (5 + (7/2)( N(N - 1) - (N / 2)(N - 1)) + 6(N - 1) +3

N =
Peor caso Mejor caso Caso medio

Complejidad del método de clasificación por   Inserción. Ο(n²)

 Ecuación temporal = 8( (N/2)(N + 1) - N) + 12(N - 1) + 4

N =

Complejidad del método de clasificación por   Quicksort. Ο(N lg(N))

 Ecuación temporal = 44 - 23 N + 13 N lg(N)

N =

Complejidad del método de clasificación por   Merge Sort. Ο(N lg(N))

 Ecuación temporal = 70 - 68N + 39 N lg(N)

N =

Complejidad de de la busqueda binaria   Busqueda Binaria. Ο(lg(N))

 Ecuación temporal = 7 + 10 lg(N)

N =

Calculadora para ayudar a determinar si existe cota Ο de:

Con ayuda de la calculadora encontrar un rango [ n₀ , n₁ ]
donde exista cota... n₁ puede ser, teoricamente ∞
Para esta calculadora, debería ser un número pequeño.

g = Ο( f )	Existe cota, si se cumple la desigualdad g <= c * f
n+10 = Ο(n2)	n+10 <= c * n2
2lg n = Ο(lg n )2	2lg n <= c * (lg n)2
√(lg n) = Ο(4lg n)	√(lg n) <= c * 4lg n
lg n = √(n)	lg n <= c * √(n)

Calculadora para buscar n y c donde exista la cota

Valor n =
Constante c =	para diferentes valores de n

Calculadora para ayudar a probar una propiedad

Primera Propiedad Ο( f ) = Ο( g ) =>      f = Ο( g ) y g = Ο( f ) Funciones ejemplo f = 3lg n y g = lg n Reemplazando en la propiedad: Prueba 3lg n = Ο( lg n ) ==>      3lg n <= c * (lg n ) Prueba lg n = Ο( 3lg n ) ==>      lg n <= c * ( 3lg n )

Calculadora para buscar n y c donde exista la cota

Valor n =
Constante c =	para diferentes valores de n

Calculadora para ayudar a probar una propiedad

Segunda Propiedad f = Ο( g ) y g = Ο( h ) =>      f = Ο( h ) Funciones ejemplo f = 3lg n , g = lg n , h = √(n) Reemplazando en la propiedad: Prueba 3lg n = Ο( √(n) ) ==>      3lg n <= c * √(n)

Calculadora para buscar n y c donde exista la cota

Valor n =
Constante c =	para diferentes valores de n

Calculadora para ayudar a probar una propiedad

Tercera propiedad. f = Ο( g ) y f = Ο( h ) =>      f = Ο( min( g, h ) ) Funciones ejemplo f = lg n , g = n2 , h = n3 Reemplazando en la propiedad: Prueba lg n = Ο( n2 ) y lg n = Ο( n3 ) ==>      lg n <= c * n2

Calculadora para buscar n y c donde exista la cota

Valor n =
Constante c =	para diferentes valores de n

Calculadora para ayudar a probar una propiedad

Cuarta Propiedad. f1 = Ο( g ) y f2 = Ο( h ) ==>      f1 + f2 = Ο( max( g, h ) ) Funciones ejemplo f1 = lg n , g = n2 , f2 = n lg n , h = n3 Reemplazando en la propiedad: Prueba lg n = Ο( n2 ) y n lg n = Ο( n3 ) ==>      ( lg n + n lg n ) <= c * n3

Calculadora para buscar n y c donde exista la cota

Valor n =
Constante c =	para diferentes valores de n

Calculadora para ayudar a probar una propiedad

Quinta Propiedad. f1 = Ο( g ) y f2 = Ο( h ) ==>      f1 * f2 = Ο( g * h ) ) Funciones ejemplo f1 = lg n , g = n2 , f2 = n lg n , h = n3 Reemplazando en la propiedad: Prueba lg n = Ο( n2 ) y n lg n = Ο( n3 ) ==>      ( ( lg n ) * ( n lg n ) ) <= c * n5

Calculadora para buscar n y c donde exista la cota

Valor n =
Constante c =	para diferentes valores de n

Calculadora para ayudar a probar una propiedad

Sexta Propiedad lim n->∞ (f / g)  = k Si k es 0 f = Ο( g ) y g ≠ Ο( f ) Si k ≠ 0 y k < ∞ Ο( f ) = Ο( g ) ( Mismo orden ) Funciones ejemplo f = n2 y g = n3 Reemplazando en la propiedad: Prueba 1. lim n->∞ ( (n2) / (n3))  = 0 Lo que implica que : n2 <= c * ( n3 )

Calculadora para buscar n y c donde exista la cota

Valor n =
Constante c =	para diferentes valores de n

Segundo ejemplo de la sexta propiedad

Funciones ejemplo f = (lg n)3 y g = n(1/3) Reemplazando en la propiedad: Prueba 2. lim n->∞ ( (lg n)3) / (n(1/3))  ≠ 0 Lo que implica que : (lg n)3 <= c * ( n(1/3) ) no siempre se cumple

Calculadora para buscar n y c donde exista la cota

Valor n =
Constante c =	para diferentes valores de n

Calculadora para ayudar a determinar si existe cota θ

Con ayuda de la calculadora encontrar un rango [ n₀ , n₁ ]
donde exista cota θ... n₁ puede ser, teoricamente ∞
Para esta calculadora, debería ser un número pequeño.

g = θ( f ) Existe cota, si se cumplen las siguientes desigualdades g <= c * f y g >= d * f para dos valores reales c y d mayores que 0.   √n = θ(lg n)   √n <= c * lg n   y   √n >= d * lg n

Calculadora para buscar n,c y d donde exista la cota

Valor n =
Constante c =	para diferentes valores de n
Constante d =	para diferentes valores de n

 Primera propiedad. Cota θ 

lim n->∞ (f / g)  = k Si k > 0 entonces: f = θ(g) Funciones ejemplo f = (lg n)3 y g = n(1/3) Reemplazando en la propiedad: lim n->∞ ( (lg n)3) / (n(1/3))  ≠ 0 Lo que implica que : (lg n)3 <= c * ( n(1/3) ) y (lg n)3 >= d * ( n(1/3) )

Calculadora para buscar n,c y d donde exista la cota

Valor n =
Constante c =	para diferentes valores de n
Constante d =	para diferentes valores de n

 Segunda propiedad. Cota θ 

Si f = θ(g) y g = θ(h) entonces: f = θ(h) Funciones ejemplo f = 2n , g = 2n+1 y h = n2 Aplicando la propiedad: 2n <= c * 2n+1 y 2n >= d * 2n+1 2n+1 <= c * n2 y 2n+1 >= d * n2 2n <= c * n2 y 2n >= d * n2

Calculadora para buscar n,c y d donde exista la cota

Valor n =
Constante c =	para diferentes valores de n
Constante d =	para diferentes valores de n

 Tercera propiedad. Regla de la suma. Cota θ 

Si f1 = θ(g) y f2 = θ(h) entonces: f1 + f2 = θ( max(g, h) ) Funciones ejemplo f1 = 3 + ln(n) , g = ln(n) f2 = 5 + ln(n) y h = 2 ln(n) Note que h, crece más rapido que g Aplicando la propiedad: 3 + ln(n) <= c * ln(n) y 3 + ln(n) >= d * ln(n) 5 + ln(n) <= c * 2 * ln(n) y 5 + ln(n) >= d * 2 * ln(n) 8 + 2 * ln(n) <= c * 2 * ln(n) y         8 + 2 * ln(n) >= d * 2 * ln(n)

Calculadora para buscar n,c y d donde exista la cota

Valor n =
Constante c =	para diferentes valores de n
Constante d =	para diferentes valores de n

 Cuarta propiedad. Regla del producto. Cota θ 

Si f1 = θ(g) y f2 = θ(h) entonces: f1 * f2 = θ( g * h ) Funciones ejemplo f1 = 3 + ln(n) , g = ln(n) f2 = 5 + ln(n) y h = 2 ln(n) 15+8*ln(n)+(ln(n))2 2 * (ln(n))2 Aplicando la propiedad: 3 + ln(n) <= c * ln(n) y 3 + ln(n) >= d * ln(n) 5 + ln(n) <= c * 2 * ln(n) y 5 + ln(n) >= d * 2 * ln(n) 15+8*ln(n)+(ln(n))2 <= c * 2 * (ln(n))2 y         15+8*ln(n)+(ln(n))2 >= d * 2 * (ln(n))2

Calculadora para buscar n,c y d donde exista la cota

Valor n =
Constante c =	para diferentes valores de n
Constante d =	para diferentes valores de n

Nota: Para solucionar las ecuaciones en recurrencia favor estudiar el capítulo 19 del texto "Estructuras de datos en C++.".