Prog2: ejercicio 2.1

Algoritmo 1:

tengo dudas de como demostrar O(n) , Ω(n) y queria saber si la siguiente demostración es correcta.

Me quedo T(n) = c1+c2+(c2+c3+c4)n

siendo c1 : asignación, c2 : comparación, c3: incremento, c4: incremento sum

dem de O:

existe c,n0 > 0 tal que T(n) <= c.n para todo n >= n0

con n0 = 1 entonces T(n0) = c1+c2+(c2+c3+c4) = c entonces T(no) <= c.n0 entonces T(n) <= c.n entonces O(n)

dem de Ω:

existe n0,k >= 0 (puede ser iguales que 0 en el caso que i > n de primera) tal que T(n) >= k.n para todo n >= n0

con n0 = 0 entonces T(n0) = c1+c2 = k entonces T(n0) >= k.n0 entonces T(n) >= k.n entonces Ω(n)

de Matias Richart - viernes, 8 de mayo de 2020, 20:38

Hola. Disculpa por la demora, se nos traspapeló tu mensaje en el foro.

Te respondo aunque está la solución colgada y capaz ya te sacaste la duda.

T(n) = c1+c2+(c2+c3+c4)n

dem de O:

existe c,n0 > 0 tal que T(n) <= c.n para todo n >= n0

con n0 = 1 entonces T(n0) = c1+c2+(c2+c3+c4) = c entonces T(no) <= c.n0 entonces T(n) <= c.n entonces O(n)

Creo que lo que haces está bien pero está un poco confuso.

Asumiendo el T(n) que tu encontraste, la demostración consiste en encontrar un c y un n0 para el que se cumpla la condición para todo n>n0

Entonces, yo lo que haría sería definir h=max{c1,c2,c3,c4} para que T(n) = c1+c2+(c2+c3+c4)n <=5hn

Por lo tanto, encontré un c=5h y un n0=1 donde se cumple que T(n)<=cn para todo n>1

dem de Ω:

existe n0,k >= 0 (puede ser iguales que 0 en el caso que i > n de primera) tal que T(n) >= k.n para todo n >= n0

con n0 = 0 entonces T(n0) = c1+c2 = k entonces T(n0) >= k.n0 entonces T(n) >= k.n entonces Ω(n)

Aquí aplicaría lo mismo, hay que encontrar el k y el n0. Con k=h (definido arriba) y n0=1 se cumple que T(n)>=kn para n>=1