Análisis de la eficiencia de un algoritmo

IIC2283

1
Una noción general de algoritmo

Sea Σ un alfabeto.

Vamos a pensar en un algoritmo A como una función A : Σ∗ → Σ∗

2
Una noción general de algoritmo

Sea Σ un alfabeto.

Vamos a pensar en un algoritmo A como una función A : Σ∗ → Σ∗

Esta es una representación general que incluye tanto a problemas de

decisión como a los de computación.
I ¿Cómo se representa un problema de decisión?

2
Tiempo de ejecución de un algoritmo

A cada algoritmo A asociamos una función tiempoA : Σ∗ → N tal que:

tiempoA (w ): número de pasos realizados por A con entrada w ∈ Σ∗

Para definir esta función tenemos que definir qué operaciones vamos a
contar, y qué costo les asignamos.

3
Tiempo de ejecución de un algoritmo en el peor caso

El primer tipo de análisis que vamos a realizar de la complejidad de un

algoritmo va a estar basado en el peor caso.

4
Tiempo de ejecución de un algoritmo en el peor caso

El primer tipo de análisis que vamos a realizar de la complejidad de un

algoritmo va a estar basado en el peor caso.

Para cada algoritmo A asociamos una función tA : N → N tal que

tA (n) = máx{tiempoA (w ) | w ∈ Σ∗ y |w | = n},

donde |w | es el largo de w

4
Notación asintótica

En muchos casos, nos interesa conocer el orden de un algoritmo en lugar

de su complejidad exacta.
I Queremos decir que un algoritmo es lineal o cuadrático, en lugar de
decir que su complejidad es 3n2 + 17n + 22

Vamos a desarrollar notación para hablar del orden de un algoritmo.

5
Notación asintótica

Supuesto
La complejidad de un algoritmo va a ser medida en términos de funciones
de la forma f : N → R+ + + +
0 , donde R = {r ∈ R | r > 0} y R0 = R ∪ {0}

6
Notación asintótica

Supuesto
La complejidad de un algoritmo va a ser medida en términos de funciones
de la forma f : N → R+ + + +
0 , donde R = {r ∈ R | r > 0} y R0 = R ∪ {0}

Estas funciones incluyen a las funciones definidas en las transparencias

anteriores, y también sirven para modelar el tiempo de ejecución de un
algoritmo

6
La notación O(f )

Sea f : N → R+
0

Definición
O(f ) = {g : N → R+ +
0 | (∃c ∈ R )(∃n0 ∈ N)
(∀n ≥ n0 ) (g (n) ≤ c · f (n))}

7
La notación O(f )

Sea f : N → R+
0

Definición
O(f ) = {g : N → R+ +
0 | (∃c ∈ R )(∃n0 ∈ N)
(∀n ≥ n0 ) (g (n) ≤ c · f (n))}

Decimos entonces que g ∈ O(f )

I También usamos la notación g es O(f ), lo cual es formalizado como
g ∈ O(f )

7
La notación O(f )

Sea f : N → R+
0

Definición
O(f ) = {g : N → R+ +
0 | (∃c ∈ R )(∃n0 ∈ N)
(∀n ≥ n0 ) (g (n) ≤ c · f (n))}

Decimos entonces que g ∈ O(f )

I También usamos la notación g es O(f ), lo cual es formalizado como
g ∈ O(f )

Ejercicio
Demuestre que 3n2 + 17n + 22 ∈ O(n2 )
Las notaciones Ω(f ) y Θ(f )

Definición
Ω(f ) = {g : N → R+ +
0 | (∃c ∈ R )(∃n0 ∈ N)
(∀n ≥ n0 ) (c · f (n) ≤ g (n))}
Θ(f ) = O(f ) ∩ Ω(f )

8
Las notaciones Ω(f ) y Θ(f )

Definición
Ω(f ) = {g : N → R+ +
0 | (∃c ∈ R )(∃n0 ∈ N)
(∀n ≥ n0 ) (c · f (n) ≤ g (n))}
Θ(f ) = O(f ) ∩ Ω(f )

Ejercicios
1. Demuestre que 3n2 + 17n + 22 ∈ Θ(n2 )

2. Demuestre que g ∈ Θ(f ) si y sólo si existen c, d ∈ R+ y

n0 ∈ N tal que para todo n ≥ n0 : c · f (n) ≤ g (n) ≤ d · f (n)

8
Ejercicios

1. Sea p(n) un polinomio de grado k ≥ 0 con coeficientes en los números

enteros. Demuestre que p(n) ∈ O(nk ).

2. ¿Cuáles de las siguientes afirmaciones son ciertas?

I n2 ∈ O(n)
I Si f (n) ∈ O(n), entonces f (n)2 ∈ O(n2 )
I Si f (n) ∈ O(n), entonces 2f (n) ∈ O(2n )

f (n)
3. Suponga que lı́m existe y es igual a `. Demuestre lo siguiente:
n→∞ g (n)
I Si ` = 0, entonces f ∈ O(g ) y g 6∈ O(f )
I Si ` = ∞, entonces g ∈ O(f ) y f 6∈ O(g )
I Si ` ∈ R+ , entonces f ∈ Θ(g )

f (n)
4. Encuentre funciones f y g tales que f ∈ Θ(g ) y lı́m no existe
n→∞ g (n)

9
Búsqueda binaria

Suponga que tiene una lista ordenada (de menor a mayor)

L[1 . . . n] de números enteros con n ≥ 1

¿Cómo podemos verificar si un número a está en L?

10
Búsqueda binaria

BúsquedaBinaria(a, L, i, j)
if i > j then return no
else if i = j then
if L[i] = a then return i
else return no
else
p := b i+j
2
c
if L[p] < a then return BúsquedaBinaria(a, L, p + 1, j)
else if L[p] > a then return BúsquedaBinaria(a, L, i, p − 1)
else return p

Llamada inicial al algoritmo: BúsquedaBinaria(a, L, 1, n)

11
Tiempo de ejecución de búsqueda binaria

¿Cuál es la complejidad del algoritmo?

I ¿Qué operaciones vamos a considerar?
I ¿Cuál es el peor caso?

12
Tiempo de ejecución de búsqueda binaria

¿Cuál es la complejidad del algoritmo?

I ¿Qué operaciones vamos a considerar?
I ¿Cuál es el peor caso?

Si contamos sólo las comparaciones, entonces la siguiente expresión

define la complejidad del algoritmo:
(
c n=1
T (n) =
T (b n2 c) + d n > 1

donde c ∈ N y d ∈ N son constantes tales que c ≥ 1 y d ≥ 1

12
Tiempo de ejecución de búsqueda binaria

¿Cuál es la complejidad del algoritmo?

I ¿Qué operaciones vamos a considerar?
I ¿Cuál es el peor caso?

Si contamos sólo las comparaciones, entonces la siguiente expresión

define la complejidad del algoritmo:
(
c n=1
T (n) =
T (b n2 c) + d n > 1

donde c ∈ N y d ∈ N son constantes tales que c ≥ 1 y d ≥ 1

Esta es una ecuación de recurrencia

12
Solucionando una ecuación de recurrencia

¿Cómo podemos solucionar una ecuación de recurrencia?

I Técnica básica: sustitución de variables
Solucionando una ecuación de recurrencia

¿Cómo podemos solucionar una ecuación de recurrencia?

I Técnica básica: sustitución de variables

Para la ecuación anterior usamos la sustitución n = 2k

I Vamos a resolver la ecuación suponiendo que n es una potencia de 2
I Vamos a utilizar inducción para demostrar que la solución obtenida
nos da el orden del algoritmo
Ecuaciones de recurrencia: sustitución de variables

Si realizamos la sustitución n = 2k en la ecuación:

(
c n=1
T (n) = n
T (b 2 c) + d n > 1

obtenemos:
(
c k=0
T (2k ) =
T (2k−1 ) + d k>0

14
Ecuaciones de recurrencia: sustitución de variables

Extendiendo la expresión anterior obtenemos:

T (2k ) = T (2k−1 ) + d
= (T (2k−2 ) + d) + d
= T (2k−2 ) + 2d
= (T (2k−3 ) + d) + 2d
= T (2k−3 ) + 3d
= ···

15
Ecuaciones de recurrencia: sustitución de variables

Extendiendo la expresión anterior obtenemos:

T (2k ) = T (2k−1 ) + d
= (T (2k−2 ) + d) + d
= T (2k−2 ) + 2d
= (T (2k−3 ) + d) + 2d
= T (2k−3 ) + 3d
= ···

Deducimos la expresión general para k − i ≥ 0:

T (2k ) = T (2k−i ) + i · d

15
Ecuaciones de recurrencia: sustitución de variables

Considerando i = k obtenemos:
T (2k ) = T (1) + k · d
= c +k ·d

16
Ecuaciones de recurrencia: sustitución de variables

Considerando i = k obtenemos:
T (2k ) = T (1) + k · d
= c +k ·d

Dado que k = log2 (n), obtenemos que T (n) = c + d · log2 (n) para n
potencia de 2

16
Ecuaciones de recurrencia: sustitución de variables

Considerando i = k obtenemos:
T (2k ) = T (1) + k · d
= c +k ·d

Dado que k = log2 (n), obtenemos que T (n) = c + d · log2 (n) para n
potencia de 2

Usando inducción vamos a extender esta solución y vamos a demostrar

que T (n) ∈ O(log2 (n))

16
Inducción constructiva

Sea T (n) definida como:

(
c n=1
T (n) =
T (b n2 c) + d n>1

Queremos demostrar que T (n) ∈ O(log2 (n))

I Vale decir, queremos demostrar que existen e ∈ R+ y n0 ∈ N tales
que T (n) ≤ e · log2 (n) para todo n ≥ n0
Inducción constructiva

Sea T (n) definida como:

(
c n=1
T (n) =
T (b n2 c) + d n>1

Queremos demostrar que T (n) ∈ O(log2 (n))

I Vale decir, queremos demostrar que existen e ∈ R+ y n0 ∈ N tales
que T (n) ≤ e · log2 (n) para todo n ≥ n0

Inducción nos va servir tanto para demostrar la propiedad y como para

determinar valores adecuados para e y n0
I Por esto usamos el término inducción constructiva
Inducción constructiva

Dado que T (1) = c y log2 (1) = 0 no es posible encontrar una valor para
e tal que T (1) ≤ e · log2 (1)

Dado que T (2) = (c + d), si consideramos e = (c + d) tenemos que

T (2) ≤ e · log2 (2)
I Definimos entonces e = (c + d) y n0 = 2

Tenemos entonces que demostrar lo siguiente:

(∀n ≥ 2)(T (n) ≤ e · log2 (n))

18
Inducción constructiva y fuerte

¿Cuál es el principio de inducción adecuado para el problema

anterior?
I Tenemos n0 como punto de partida

I n0 es un caso base, pero podemos tener otros

I Dado n > n0 tal que n no es un caso base, suponemos que la

propiedad se cumple para todo k ∈ {n0 , . . . , n − 1}

19
Inducción constructiva y fuerte

Queremos demostrar que (∀n ≥ 2) (T (n) ≤ e · log2 (n))

20
Inducción constructiva y fuerte

Queremos demostrar que (∀n ≥ 2) (T (n) ≤ e · log2 (n))

I 2 es el punto de partida y el primer caso base

20
Inducción constructiva y fuerte

Queremos demostrar que (∀n ≥ 2) (T (n) ≤ e · log2 (n))

I 2 es el punto de partida y el primer caso base

I También 3 es un caso base ya que T (3) = T (1) + d y para

T (1) no se cumple la propiedad

20
Inducción constructiva y fuerte

Queremos demostrar que (∀n ≥ 2) (T (n) ≤ e · log2 (n))

I 2 es el punto de partida y el primer caso base

I También 3 es un caso base ya que T (3) = T (1) + d y para

T (1) no se cumple la propiedad

I Para n ≥ 4 tenemos que T (n) = T (b n2 c) + d y b n2 c ≥ 2, por

lo que resolvemos este caso de manera inductiva
I Suponemos que la propiedad se cumple para todo
k ∈ {2, . . . , n − 1}

20
La demostración por inducción fuerte

Casos base:
T (2) = c +d = e · log2 (2)
T (3) = c +d < e · log2 (3)

21
La demostración por inducción fuerte

Casos base:
T (2) = c +d = e · log2 (2)
T (3) = c +d < e · log2 (3)

Caso inductivo:

Suponemos que n ≥ 4 y para todo k ∈ {2, . . . , n − 1} se

tiene que T (k) ≤ e · log2 (k)

21
La demostración por inducción fuerte

Usando la definición de T (n) y la hipótesis de inducción concluimos que:

n
T (n) = T (b c) + d
2
n
≤ e · log2 (b c) + d
2
n
≤ e · log2 ( ) + d
2
= e · log2 (n) − e · log2 (2) + d
= e · log2 (n) − (c + d) + d
= e · log2 (n) − c
< e · log2 (n)

22
Un segundo ejemplo de inducción constructiva

Considere la siguiente ecuación de recurrencia:

(
0 n=0
T (n) = 2
n + n · T (n − 1) n > 0
Un segundo ejemplo de inducción constructiva

Considere la siguiente ecuación de recurrencia:

(
0 n=0
T (n) = 2
n + n · T (n − 1) n > 0

Queremos determinar una función f (n) para la cual se tiene que

T (n) ∈ O(f (n))
Un segundo ejemplo de inducción constructiva

Considere la siguiente ecuación de recurrencia:

(
0 n=0
T (n) = 2
n + n · T (n − 1) n > 0

Queremos determinar una función f (n) para la cual se tiene que

T (n) ∈ O(f (n))
I ¿Alguna conjetura sobre quién podrı́a ser f (n)?

23
Una posible solución para la ecuación de recurrencia

Dada la forma de la ecuación de recurrencia, podrı́amos intentar

primero con f (n) = n!

Tenemos entonces que determinar c ∈ R+ y n0 ∈ N tales que

T (n) ≤ c · n! para todo n ≥ n0
Una posible solución para la ecuación de recurrencia

Dada la forma de la ecuación de recurrencia, podrı́amos intentar

primero con f (n) = n!

Tenemos entonces que determinar c ∈ R+ y n0 ∈ N tales que

T (n) ≤ c · n! para todo n ≥ n0
I Pero nos vamos a encontrar con un problema al tratar de usar
la hipótesis de inducción
Una posible solución para la ecuación de recurrencia

Supongamos que la propiedad se cumple para n:

T (n) ≤ c · n!
Una posible solución para la ecuación de recurrencia

Supongamos que la propiedad se cumple para n:

T (n) ≤ c · n!

Tenemos que:
T (n + 1) = (n + 1)2 + (n + 1) · T (n)
≤ (n + 1)2 + (n + 1) · (c · n!)
= (n + 1)2 + c · (n + 1)!

25
Una posible solución para la ecuación de recurrencia

Supongamos que la propiedad se cumple para n:

T (n) ≤ c · n!

Tenemos que:
T (n + 1) = (n + 1)2 + (n + 1) · T (n)
≤ (n + 1)2 + (n + 1) · (c · n!)
= (n + 1)2 + c · (n + 1)!

Pero no existe una constante c para la cual (n + 1)2 + c · (n + 1)! ≤ c · (n + 1)!

I Dado que n ∈ N

25
¿Cómo solucionamos el problema con la demostración?

Una demostración por inducción puede hacerse más simple considerando

una propiedad más fuerte.
I Dado que la hipótesis de inducción se va a volver más fuerte

26
¿Cómo solucionamos el problema con la demostración?

Una demostración por inducción puede hacerse más simple considerando

una propiedad más fuerte.
I Dado que la hipótesis de inducción se va a volver más fuerte

Vamos a seguir tratando de demostrar que T (n) ∈ O(n!) pero ahora

considerando una propiedad más fuerte.

26
¿Cómo solucionamos el problema con la demostración?

Una demostración por inducción puede hacerse más simple considerando

una propiedad más fuerte.
I Dado que la hipótesis de inducción se va a volver más fuerte

Vamos a seguir tratando de demostrar que T (n) ∈ O(n!) pero ahora

considerando una propiedad más fuerte.

Vamos a demostrar lo siguiente:

(∃c ∈ R+ )(∃d ∈ R+ )(∃n0 ∈ N)(∀n ≥ n0 )(T (n) ≤ c · n! − d · n)

26
Inducción constructiva sobre una propiedad más fuerte
Para tener una mejor idea de los posible valores para c, d y n0 vamos a
considerar primero el paso inductivo en la demostración.

27
Inducción constructiva sobre una propiedad más fuerte
Para tener una mejor idea de los posible valores para c, d y n0 vamos a
considerar primero el paso inductivo en la demostración.

Supongamos que la propiedad se cumple para n:

T (n) ≤ c · n! − d · n

27
Inducción constructiva sobre una propiedad más fuerte
Para tener una mejor idea de los posible valores para c, d y n0 vamos a
considerar primero el paso inductivo en la demostración.

Supongamos que la propiedad se cumple para n:

T (n) ≤ c · n! − d · n

Tenemos que:
T (n + 1) = (n + 1)2 + (n + 1) · T (n)
≤ (n + 1)2 + (n + 1) · (c · n! − d · n)
= c · (n + 1)! + (n + 1)2 − d · n · (n + 1)
= c · (n + 1)! + ((n + 1) − d · n) · (n + 1)

27
Inducción constructiva sobre una propiedad más fuerte

Para poder demostrar que la propiedad se cumple para n + 1 necesitamos

que lo siguiente sea cierto:

(n + 1) − d · n ≤ −d
Inducción constructiva sobre una propiedad más fuerte

Para poder demostrar que la propiedad se cumple para n + 1 necesitamos

que lo siguiente sea cierto:

(n + 1) − d · n ≤ −d

De lo cual concluimos la siguiente restricción para d:

(n + 1)
≤ d
(n − 1)
Inducción constructiva sobre una propiedad más fuerte

Para poder demostrar que la propiedad se cumple para n + 1 necesitamos

que lo siguiente sea cierto:

(n + 1) − d · n ≤ −d

De lo cual concluimos la siguiente restricción para d:

(n + 1)
≤ d
(n − 1)

Si consideramos n ≥ 2 concluimos que d ≥ 3

I Consideramos entonces n0 = 2 y d = 3
Inducción constructiva sobre una propiedad más fuerte

Para concluir la demostración debemos considerar el caso base n0 = 2

Inducción constructiva sobre una propiedad más fuerte

Para concluir la demostración debemos considerar el caso base n0 = 2

Tenemos que:
T (0) = 0
T (1) = 12 + 1 · T (0) = 1
T (2) = 22 + 2 · T (1) = 6
Inducción constructiva sobre una propiedad más fuerte

Para concluir la demostración debemos considerar el caso base n0 = 2

Tenemos que:
T (0) = 0
T (1) = 12 + 1 · T (0) = 1
T (2) = 22 + 2 · T (1) = 6

Entonces se debe cumplir que T (2) ≤ c · 2! − 3 · 2, vale decir,

6 ≤ c ·2−6
Inducción constructiva sobre una propiedad más fuerte

Para concluir la demostración debemos considerar el caso base n0 = 2

Tenemos que:
T (0) = 0
T (1) = 12 + 1 · T (0) = 1
T (2) = 22 + 2 · T (1) = 6

Entonces se debe cumplir que T (2) ≤ c · 2! − 3 · 2, vale decir,

6 ≤ c ·2−6

Concluimos que c ≥ 6, por lo que consideramos c = 6

I Tenemos entonces que (∀n ≥ 2)(T (n) ≤ 6 · n! − 3 · n), de lo cual
concluimos que T (n) ∈ O(n!)
El Teorema Maestro

Muchas de las ecuaciones de recurrencia que vamos a usar en este curso

tienen la siguiente forma:
(
c n=0
T (n) = n
a · T (b b c) + f (n) n ≥ 1

donde a, b y c son constantes, y f (n) es una función arbitraria.

El Teorema Maestro nos dice cuál es el orden de T (n) dependiendo de

ciertas condiciones sobre a, b y f (n)

30
El Teorema Maestro

El Teorema Maestro también se puede utilizar cuando b bn c es

reemplazado por d bn e

Antes de dar el enunciado del Teorema Maestro necesitamos definir una

condición de regularidad sobre la función f (n)

31
Una condición de regularidad sobre funciones

Dado: función f : N → R+
0 y constantes a, b ∈ R tales que a ≥ 1 y b > 1

Definición
f es (a, b)-regular si existen constantes c ∈ R+ y n0 ∈ N tales que c < 1 y
n
(∀n ≥ n0 )(a · f (b c) ≤ c · f (n))
b
Una condición de regularidad sobre funciones

Dado: función f : N → R+
0 y constantes a, b ∈ R tales que a ≥ 1 y b > 1

Definición
f es (a, b)-regular si existen constantes c ∈ R+ y n0 ∈ N tales que c < 1 y
n
(∀n ≥ n0 )(a · f (b c) ≤ c · f (n))
b

Ejercicio
1. Demuestre que las funciones n, n2 y 2n son (a, b)-regulares si a < b.
2. Demuestre que la función log2 (n) no es (1,2)-regular.
Una solución al segundo problema

Por contradicción, supongamos que log2 (n) es (1,2)-regular.

Entonces existen constantes c ∈ R+ y n0 ∈ N tales que c < 1 y

n
(∀n ≥ n0 )(log2 (b c) ≤ c · log2 (n))
2

33
Una solución al segundo problema

Por contradicción, supongamos que log2 (n) es (1,2)-regular.

Entonces existen constantes c ∈ R+ y n0 ∈ N tales que c < 1 y

n
(∀n ≥ n0 )(log2 (b c) ≤ c · log2 (n))
2

De esto concluimos que:

2·k
(∀k ≥ n0 )(log2 (b c) ≤ c · log2 (2 · k))
2
Una solución al segundo problema

Vale decir:
(∀k ≥ n0 )(log2 (k) ≤ c · (log2 (k) + 1))
Una solución al segundo problema

Vale decir:
(∀k ≥ n0 )(log2 (k) ≤ c · (log2 (k) + 1))

Dado que 0 < c < 1, concluimos que:

c
(∀k ≥ n0 )(log2 (k) ≤ )
1−c
Lo cual nos lleva a una contradicción.

34
El enunciado del Teorema Maestro

Teorema
Sea f : N → R+ +
0 , a, b, c ∈ R0 tales que a ≥ 1 y b > 1, y T (n) una función
definida por la siguiente ecuación de recurrencia:
(
c n=0
T (n) =
a · T (b bn c) + f (n) n ≥ 1

Se tiene que:
El enunciado del Teorema Maestro

Teorema
Sea f : N → R+ +
0 , a, b, c ∈ R0 tales que a ≥ 1 y b > 1, y T (n) una función
definida por la siguiente ecuación de recurrencia:
(
c n=0
T (n) =
a · T (b bn c) + f (n) n ≥ 1

Se tiene que:
1. Si f (n) ∈ O(nlogb (a)−ε ) para ε > 0, entonces T (n) ∈ Θ(nlogb (a) )
El enunciado del Teorema Maestro

Teorema
Sea f : N → R+ +
0 , a, b, c ∈ R0 tales que a ≥ 1 y b > 1, y T (n) una función
definida por la siguiente ecuación de recurrencia:
(
c n=0
T (n) =
a · T (b bn c) + f (n) n ≥ 1

Se tiene que:
1. Si f (n) ∈ O(nlogb (a)−ε ) para ε > 0, entonces T (n) ∈ Θ(nlogb (a) )
2. Si f (n) ∈ Θ(nlogb (a) ), entonces T (n) ∈ Θ(nlogb (a) · log2 (n))
El enunciado del Teorema Maestro

Teorema
Sea f : N → R+ +
0 , a, b, c ∈ R0 tales que a ≥ 1 y b > 1, y T (n) una función
definida por la siguiente ecuación de recurrencia:
(
c n=0
T (n) =
a · T (b bn c) + f (n) n ≥ 1

Se tiene que:
1. Si f (n) ∈ O(nlogb (a)−ε ) para ε > 0, entonces T (n) ∈ Θ(nlogb (a) )
2. Si f (n) ∈ Θ(nlogb (a) ), entonces T (n) ∈ Θ(nlogb (a) · log2 (n))
3. Si f (n) ∈ Ω(nlogb (a)+ε ) para ε > 0 y f es (a, b)-regular, entonces
T (n) ∈ Θ(f (n))
Usando el Teorema Maestro

Considere la siguiente ecuación de recurrencia:

(
1 n=0
T (n) =
3 · T (b n2 c) + c · n n≥1
Usando el Teorema Maestro

Considere la siguiente ecuación de recurrencia:

(
1 n=0
T (n) =
3 · T (b n2 c) + c · n n≥1

Dado que log2 (3) > 1.5, tenemos que log2 (3) − 0.5 > 1
Usando el Teorema Maestro

Considere la siguiente ecuación de recurrencia:

(
1 n=0
T (n) =
3 · T (b n2 c) + c · n n≥1

Dado que log2 (3) > 1.5, tenemos que log2 (3) − 0.5 > 1

Deducimos que c · n ∈ O(nlog2 (3)−0.5 ), por lo que usando el Teorema

Maestro concluimos que T (n) ∈ Θ(nlog2 (3) )
El Teorema Maestro y la función dxe

Suponga que cambiamos b bn c por d bn e en la definición de

(a, b)-regularidad.

Entonces el Teorema Maestro sigue siendo válido pero con

T (b bn c) + f (n) reemplazado por T (d bn e) + f (n)

37
Analizando la complejidad de un algoritmo

Sea A : Σ∗ → Σ∗ un algoritmo
I Recuerde que tA (n) es el mayor número de pasos realizados por A
sobre las entradas w ∈ Σ∗ de largo n

Definición (Complejidad en el peor caso)

Decimos que A en el peor caso es O(f (n)) si tA (n) ∈ O(f (n))

38
Analizando la complejidad de un algoritmo

Notación
Las definición de peor caso puede ser modificada para considerar las
notaciones Θ y Ω
I Simplemente reemplazando O(f (n)) por Θ(f (n)) u Ω(f (n)),
respectivamente

Por ejemplo, decimos que A en peor caso es Ω(f (n)) si tA (n) ∈ Ω(f (n))

39