Práctica 2: Complejidad (Algoritmos III)

De Cuba-Wiki

Ejercicio 02.01:

log(2,n)

Ejercicio 02.02:

No. Base 1 requiere espacio O(n), y las demas O(log n)

Ejercicio 02.03:


a)
b)
c)

Ejercicio 02.04:


a)
i. f = n <= 1*n (todo n) -> f es O(n)
ii. f = 3*n^2 + 7*n + 4 <= 4*n^2 (n>=8) -> f es O(n^2)
iii.f = n^i <= 1*n^j (todo n) <=> i < j -> f es O(n^j) <=> i < j
iv. f = n*log n <= 1*n^2 (todo n) -> f es O(n^2)


b) Sup. Ex. k en R / n! <= k* r^n <=> n!/r^n <= k. Pero lim{n->∞} n!/r^n = ∞ (ABS)

Ejercicio 02.05:


a)
b)
c)
d)

Ejercicio 02.06:


a)
b)
c)

Ejercicio 02.07:


a)
b)
c)
d)

Ejercicio 02.08:


a)
b)
c)

Ejercicio 02.09:


a)
b)
c)
d)

Ejercicio 02.10:


a)
b)
c)
d)
e)

Ejercicio 02.11:

Ejercicio 02.12:

Ejercicio 02.13:


a)
b)
c)

Ejercicio 02.14:


a)
b)
c)
d)
e)
f)

Ejercicio 02.15:


a)
b)
c)

Ejercicio 02.16:


a)
b)
c)
d)
e)

Ejercicio 02.17:


a)
b)
c)

Ejercicio 02.18:


a)
b)
c)

Ejercicio 02.19:


a)
b)
c)

Ejercicio 02.20:

Ejercicio 02.21:

Ejercicio 02.22:


a) Algoritmo:

1.si (actual != b)
	avanzo
2.sino
	volver 1 lugar hacia atras
3.si (cinta == ultimo guardado)
	tachamoa cinta con b
	nos movemos al anterior y guardamos
	(pero si es blanco ir a SI)
	volvemos a 1
sino
	ir a NO


b)