Complejidad

Complejidad

By Enrique Ferreiro

Multiple Select

Para la siguiente función, ¿Cuál podría ser su complejidad en el peor caso?

• $$O\left(n^2\right)$$  

• $$O\left(1\right)$$  

• $$\Omega\left(n\log n\right)$$  

• $$\theta\left(n^2\right)$$  

Multiple Select

Para la misma función, con n = 1, ¿Cuál sería el mejor caso de complejidad?

• $$O\left(n\right)$$  

• $$\theta\left(n^2\right)$$  

• $$\theta\left(n\right)$$  

• $$O\left(n^2\right)$$  

Multiple Choice

La siguiente definición corresponde a:

$$\forall n,\ n\ge N,\ g\left(n\right)\le c\cdot f\left(n\right)$$ a partir de alguna N 

• $$o\left(f\left(n\right)\right)$$  

• $$O\left(f\left(n\right)\right)$$  

• $$\theta\left(f\left(n\right)\right)$$  

• $$\Omega\left(f\left(n\right)\right)$$  

• $$\omega\left(f\left(n\right)\right)$$  

Open Ended

A simple vista, ¿Qué puedes decir de g(x)?

Multiple Choice

¿Es posible afirmar para la función $$g\left(x\right)$$  anterior que $$g\left(x\right)\in O\left(f\left(n\right)\right)$$  ?

• No, es posible

• Por su pollo

• Si y no, depende de ciertas condiciones

• Depende la especie

Home

Open in new tab

Copy link

Open Ended

Ahora, ¿Qué puedes decir de $$g\left(x\right)$$  ?

Home

Open in new tab

Copy link

Multiple Choice

En las gráficas anteriores, existía una constate tal que: $$0\ <c\ \le0.7$$  para la cual podemos decir que:

• $$g\left(n\right)\in\ O\left(f\left(n\right)\right)$$  

• $$f\left(n\right)\in\ \Omega\left(g\left(n\right)\right)$$  

• $$g\left(n\right)\in\ \Omega\left(f\left(n\right)\right)$$  

• $$f\left(n\right)\in\ O\left(g\left(n\right)\right)$$