Cotas

¿Cuáles de estas afirmaciones son verdaderas? Recordá: la consigna asume que se busca una cota ajustada, no la más grande posible.

$n\in O(1)$

Ver respuesta

Falso. $O(1)$ significa tiempo constante. $n$ crece sin límite, no puede estar acotada por una constante. Para cota ajustada, $n\in O(n)$.

---

$500\in O(n)$

Ver respuesta

Verdadero pero no es cota ajustada. $500$ es constante, así que $500\in O(1)$. Decir $O(n)$ es correcto matemáticamente ($500\le c\cdot n$ para todo $n\ge 1$ con $c=500$), pero no es ajustado.

---

$4n\in O(4^n)$

Ver respuesta

Falso como cota ajustada. $4n$ crece linealmente, no exponencialmente. La cota ajustada es $O(n)$, no $O(4^n)$. $O(4^n)$ sería una cota correcta pero muy holgada.

---

$n^2+\frac{1}{5}{n}^3\in O(n^3)$

Ver respuesta

Verdadero. El término dominante es $n^3$. $n^2+\frac{1}{5}{n}^3\le c\cdot n^3$ para $c=1$ y $n\ge 1$. Como el término dominante es exactamente $n^3$, $O(n^3)$ es además la cota ajustada.

---

$n\cdot (n+2{)}^{2/3}\in O(n^2)$

Ver respuesta

Falso como cota ajustada. $n\cdot (n+2{)}^{2/3}\approx n^{1+2/3}=n^{5/3}$. La cota ajustada es $O(n^{5/3})$, no $O(n^2)$. $O(n^2)$ sería válida pero no ajustada.

---

$2\cdot {\log }_{2}n\in O({\log }_{4}n)$

Ver respuesta

Verdadero. ${\log }_{4}n=\frac{{\log }_{2}n}{{\log }_{2}4}=\frac{{\log }_{2}n}{2}$. Entonces $2\cdot {\log }_{2}n=4\cdot {\log }_{4}n$. Son proporcionales: ambos crecen igual de rápido. $O(\log n)$ es la misma clase sin importar la base.

---

$3^n\in O(2^n)$

Ver respuesta

Falso. $3^n/2^n=(3/2{)}^n\to \infty$. Es decir, $3^n$ crece mucho más rápido que $2^n$, no puede estar acotada por ella. $O(3^n)\not\subset O(2^n)$.