Sistemas Operativos

Introducción teórica:

Previo a resolver los ejercicios pondremos un poco de teoría, que nos vendrá bien para luego hacer los ejercicios:

Empezaremos viendo las distintas notaciones, para “el orden de”, cota inferior y orden exacto:

- Notación para el orden de (cota superior):

Es conveniente disponer de un símbolo matemático para representar el orden de. Sea: ℕ → ℝ una función arbitraria de los números naturales en los reales no negativos. Le indicará mediante () el conjunto de todas las funciones

:ℕ → ℝ tales que t (n) ≤c ∗f(n), para todo n ≥n0 para una constante positiva c y un umbral entero . En otras palabras: 0(f(n)) ≡ {t:ℕ → ℝ>0|∃ ∈ ℝ, n0∈ ℕ,∀n ≥n0|t(n) ≤ c∗f(n)}

Gráficamente sería:

Siendo:

N0: Cierto umbral del tamaño del problema.

f(n): Acota superiormente a la función ().

- Notación para la cota inferior:

Matemáticamente, esto significa que existe una constante real positiva y un umbral entero n0 tal que t(n) ≥d ∗f(n) siempre que n≥ n0

Ω(f(n)) ≡ {t:ℕ → ℝ>0|∃ d ∈ ℝ+, n0 ∈ ℕ,∀n ≥ n0|t(n) ≥ d∗f(n)}

Gráficamente sería:

- Notación para el orden exacto:

Diremos que t(n) está en Theta de f(n), o lo que es igual que t(n) está en el orden exacto de f(n) y lo denotamos t(n) ∈ (f(n)), si t(n) pertenece tanto a

0(f(n)) como a Ω(f(n)).

La definición formal de

...