Algoritmos y estructuras de datos

T#3: 1.

Para la solución de este problema, se tiene que un orden total es un orden parcial, y que a la vez corresponde a una relación total, es decir, Para todo a,b en A: a R b || b R a. Una relación es un orden parcial si es reflexiva, antisimétrica y transitiva. En este caso, se puede asumir que la relación es “Es tan buena o mejor”.

Reflexivo:

Esto es un poco trivial, pero todo mundo es tan bueno o menos que ellos mismos.

Transitivo:

Si A es mejor que B y B es mejor que C, entonces A es mejor que C.

Antisimétrico:

Si A es mejor que B, entonces B no es mejor que A. Por lo tanto, hasta ahora se tiene un orden parcial. Dado que asumimos que podemos comparar dos candidatos, entonces la comparación debe ser una relación total y por lo tanto tenemos un orden total.

T#3: 2.

Sin pérdida de generalidad podemos suponer que

RANDOM(a,b){

   n=↳log(b)↲+1
   Inicializar un arreglo A con longitud n
   While True do
      for i=1 to n do
          A[i]=RANDOM(0,1)
      end for
      if A mantiene la representación binaria de un número menor o igual que B, entonces
         Regresa número representado por A
      end if
      end while} 
Cada iteración del ciclo While toma O(n) tiempo de ejecución. La probabilidad de que el ciclo While es una iteración dada es b+1/2^n . Así, el tiempo de ejecución esperado es el número esperado de iteraciones del tiempo n del ciclo While. Esto está dado por:

En la configuración inicial del problema, el tiempo de ejecución del algoritmo se convierteO(log(b-a)) desde que se asume a=0 al inicio.

T#3: 3.

El caso de que se contrate solo una vez: La probabilidad de que se contrate exactamente una vez corresponde al evento en el que el mejor candidato sea entrevistado primero. La probabilidad de este evento es 1/n. • El caso de que se contrate a todos: La probabilidad de que se contrate a todos los n candidatos corresponde al evento en que los candidatos son entrevistados en un orden ascendente (Del más débil al más fuerte). Por lo tanto, la probabilidad de este evento es 1/n!.

T#3: 4.

Se contrata dos veces cuando la primera contratación es el candidato con rango i y todos los candidatos con rango k>i vienen después del candidato con rango n. Hay n-1 candidatos más apropiados y la probabilidad de que el mejor venga primero es 1/(n-i) (Se puede ignorar los otros candidatos y no afectan la probabilidad). Por lo tanto, la probabilidad de contratar dos veces si el primer candidato tiene rango i es:  

La primera parte refleja la probabilidad de escoger a ese candidato particular de n. la probabilidad de contratar 2 veces es:

T#3: 5.

Sean  las variables aleatorias para calcular el valor esperado que cuenta el número de veces que aparecen las caras 1,2,3,...,6. Sea x la variable aleatoria correspondiente a la suma de n dados.

. El valor esperado  es

Por lo tanto,

T#3: 6.

Este problema se resuelve utilizando variables aleatorias indicadoras. Para  , sean :

 {Cliente i que recibe su propio sombrero}

Sea la variable aleatoria X el número de clientes que reciben su propio sombrero devuelta. Se desea calcular E[X], de la siguiente manera:

Es fácil ver que la probabilidad de que el cliente i reciba su propio sombrero es 1/n. Esto implica que  , por propiedades básicas de variables indicadoras aleatorias (Lema 5.1 en el libro de Cormen). Se tiene que:

Por lo tanto, el número esperado de clientes que reciben sus propios sombreros es de 1. Hay que tener en cuenta que  es la linealidad de la esperanza. Es importante observar también que la linealidad de la esperanza se mantiene incluso cuando las variables aleatorias no son independientes. Las  en este problema no son independientes, lo que se ve fácilmente en el caso cuando n=2. En este caso, si el cliente 1 recibe su propio sombrero nuevamente, entonces el cliente 2 debe obtener su propio sombrero de nuevo también, ya que no hay otro cliente que lo pueda recibir.

T#3: 7.

Para

 es la variable indicadora aleatoria para el evento donde es el par (i,j), con , es invertido. Ahora  es igual a 1/2, porque en cualquier permutación aleatoria de n números distintos, hay precisamente dos posibilidades,  y , teniendo cada uno de estos una probabilidad igual a 1/2, es decir, .

Sea X la variable aleatoria que denota el número total de pares invertidos en el arreglo, entonces la solución al problema es E[X]. Nótese que X es igual a la suma de todas las . El número total de inversiones es claramente:

Se deduce que el número esperado de inversiones es:

T#3: 8.

Para la solución de este ejercicio, se procede por inducción sobre n. Si n=2, la ecuación es

Suponiendo que n>2. Sea . Entonces, se usará la ecuación antes mencionada seguida por la hipótesis de inducción para obtener lo siguiente:

T#3: 9.

No. En cada una de las n iteraciones el algoritmo elige el índice  independiente y uniformemente al azar del conjunto . Esto significa que hay  diferentes secuencias posibles donde cada una tiene probabilidad de . Por otro lado, hay  permutaciones distintas, y para obtener una distribución uniforme sobre permutaciones, la probabilidad de cada uno debe ser . Por lo tanto, se debe tener  donde  es un entero. Pero no es posible en general, ya que regularmente  no es divisible por n!.

T#3: 10.

Para  tal que , sea  que denota el evento donde los elementos  y  son idénticos. Puesto que los elementos en P se eligen independientemente y uniformemente al azar de los valores  a , se tiene  para todos los pares . El hecho de que no todos los elementos son únicos, es decir, hay al menos un par de elementos idénticos, es  Por lo tanto, la probabilidad de que todos los elementos sean únicos es:

T#1: 1.

Considérese el árbol de decisiones de un algoritmo basado en comparaciones sin información adicional de los elementos. Nótese que para que el algoritmo sea correcto, dado que no tiene información adicional, todas las posibles permutaciones de los elementos deben ser hojas. Además, como el algoritmo es basado en comparaciones, este árbol es binario. Por lo tanto, si se necesitan ordenar n elementos, el árbol binario de decisiones debe tener al menos n! hojas, y dado que es binario, una altura de Γlog (n!)Γ. Por tal, la altura corresponde a la cantidad de comparaciones necesarias para ordenar los n elementos en el peor caso. Concluyendo con lo siguiente: Γlog(5!)Γ= 7 comparaciones para ordenar 5 elementos.

Sean {a, b, c, d, e} los 5 elementos

- Primero agrupar pares de números: (a,b),(c,d)

– Comparar pares para ordenarlos: a

– Comparar los elementos más pequeños de los pares, obtenemos un resultado: a

– Comparar el elemento e, con el elemento más grande en la última comparación (c).

    -Si e,>

    -Si e>c entonces se debería ordenar (b,c,d,e) debido a  a que se sabe que c

            Comparar (d,e), si d

                        Comparar(b,d), si b>d

                                   Comparar(b,e). Finaliza

                        Si b

                                    Comprar(b,c). Finaliza

            Si d

                        Comparar (b,e), si b>e

                                   Comparar (b,d). Finaliza

                        Si b

                                   Comprar(b,c). Finaliza

T#1: 4. a) Se puede asumir que k es una potencia de 2; por otro lado, se pueden agregar nuevas entradas al final del arreglo de entrada, cada uno con valor de ∞. Podemos usar el siguiente algoritmo recursivo SELECT (A,r) regresa el índice del r-esimo elemento más pequeño del arreglo A, esto en O(n). PARTITION(A,p) es la subrutina de partición del QuickSort, el cual también ejecuta en O(n).

BLOCKSORT(A[1...n],k):

            If k=1{ Regresa A }

            r = n/2

            PARTITION(A,SELECT(A,r))

            BLOCKSORT (A[1...n],k/2)

            BLOCKSORT(A[r+1,...n],k/2)

Sea T(k, ‘) el tiempo requerido para la partición de un arreglo de tamaño k’ en k bloques de longitud ‘. Esta función satisface la recurrencia:

O if k=1

T(k,’)=2t(k>

La solución sería T(k,’)=O(k’logk). Siendo el tiempo de ejecución T(k,n/k)=O(nlogk)

b) Considérese cualquier árbol de decisión que represente un algoritmo k-sorting. Cada hoja está etiquetada con un vector (b₁,b₂,…,b_n) donde cada b_i es un entero entre 1 y k, e indica que bloque contiene a A[i]. El número de posibles salidas del vector es:

n                   =      n!/(n/k)!^k = (n/e)ⁿ/((n/ke)^n/k)^k=kⁿ

n/k n/k …

Entonces cualquier árbol de decisión debe tener al menos esa cantidad de hojas. Por lo tanto, la profundidad de cualquier árbol de decisión debe ser al menos log₂kⁿ= (nlogk).

c) Se podrían tomar todos los elementos de cada uno de los bloques, y ponerlos como hojas de un min-heap, lo cual se ejecuta en O(logn/k). Posteriormente, se realiza un ordenamiento tomando un tiempo de O(nlogn/k).

T#1: 5. Para comprobar si m es de O(n²), y ejecuta en tiempo lineal se pude considerar el siguiente algoritmo:

1. Creamos un arreglo x de tamaño. // X[i]=0 para i ∈ {1,2,..,n}

2. Si a₁,…,a_n son los elementos a ordenar. // Para cada i ∈ {1,…,n} //r_i =a_i %n (r_i es el residuo de dividir a_i entre n) // x[r_i +1]=x[r_i + 1]+1

Notese que r_i ∈ {0,…,n-1}(Por ser un residuo de dividir entre n).  // Y al finalizar esta operación x[i] almacena la cantidad de elementos que tienen el residuo i-1. Esto es por la siguiente invariante de ciclo: // x[i] almacena la cantidad de elementos visitados con residuo i-1. // Al inicio no se ha visitado ningún elemento, por lo tanto x[i] debe ser 0 para todo i ∈{1,…,n}. Esto se garantiza en el paso 1. // Para los algoritmos se consideran arreglos con índices que inician en 1 y terminan en n. Si la invariante se mantiene hasta un paso k y visitamos el elemento a_k+1 , x[r_k+1+1] contiene, al inicio de este paso, la cantidad de elementos con residuo r_k+1 hasta el paso k. Dados que a_k+1 tiene residuo r_k+1 , la cantidad de elementos con residuo r_k+1 hasta el paso k+1 debe ser x[r_k+1+1]+1. Esto es exactamente lo que hace el algoritmo. Además los residuos se mantienen.

3. Creamos un arreglo Y de tamaño n. // Y[1]=1

4. Para cada i ∈ {2,…,n} // Y[i]=Y[i-1]+Y[i-1] // Nótese que Y[i] indica la posición que debe ocupar un elemento con residuo i-1 al ordenarlos por residuos.

// Y[i], el primer residuo debe ir en la posición 1 del arreglo. // Y[i+1] el residuo i+1 debe ir en el lugar del residuo anterior, Y[i] sumando a la cantidad de elementos con residuo i.

Se crea un arreglo A de tamaño n.

Para cada i ∈ {1,…,n} // r_i=a_i // A[Y[r_i+1]]=a_i // Y[r_i+1]=Y[r_i+1]+1

A tiene los elementos ordenados por residuos, dado que Y[r_i+1] indica la posición de un elemento con residuo r_i , al agregar dicho elemento, se debe actualizar y recorrer un lugar ya que el lugar anterior ya se ocupó.

T#1: 5(Continuación).

Este algoritmo es estable ya que si dos elementos tienen el mismo residuo, el que aparece primero se coloca primero. A este algoritmo se le conoce como Counting Sort (Ordenado con respecto a las residuos) y corre en tiempo O(n). // 1. Ocupa n operaciones (una para cada elemento de X) // 2. Ocupa 2n operaciones (2 por cada i ∈ {1,…,n}). // 3. Ocupa n+1 operaciones (reservar el arreglo y llenar la primera posición). //4. Ocupa n operaciones. // 5. Ocupa 3n operaciones. // Nótese que cada uno de los pasos previos ocupa a lo más O(n) operaciones. Entonces de 1 a 5 ocupa O(5n)=O(n) operaciones. A continuación se ordena el arreglo A con respecto a los factores de dividir entre n a los números.

6. Se crea un arreglo X₁ de tamaño n+1 // X₁[i]=0 para cada i ∈{1,…,n}

7. Para cada i ∈{1,…,n+1} // f_i=A[i]/n (División entera) // X₁[f_i+1]=X₁[f_i+1]+1 // Nótese que fi ∈{0,…,n} dado que A[i] ∈{1,…,n²}

8. Se crea un arreglo Y1 de tamaño n+1 // Y₁[1]=1

9. Para cada i ∈ {2,…,n+1} // Y₁[i]=Y₁[i+1]+X₁[i-1]

10. Se crea A_1, un arreglo de tamaño n. // Para cada i E {1,…,n+1}: // fi=A[i] // A₁[Y₁[f_i+1]]=A[i] // Y₁[f_i+1]=Y₁[f_i+1]+1

A₁ tiene a los elementos ordenados. Véase que del paso 6 al 10 se ordena por factores a los elementos y del 1 al 5 por residuos. Y también que cada elemento a se expresa de la forma a=nf_a+r_a . Además como 0_a,>_b,>+r_b y f_b > f_a , entonces b>a. Por otro lado, si f_b=f_a y r_b>r_a , entonces b>a.

De estas observaciones y que Counting Sort es estable, se sigue que al ordenarlos primero por residuos y posteriormente por factores, se ordena el conjunto de números. Además del paso 6 al 10 es idéntico de 1 al 5, excepto por la operación división que reemplaza a la operación módulo. Es decir, de 1 a 5 es de O(n), por lo tanto, de 6 a 10 también. Esto implica que la complejidad total (de 1 a 10) es de O(n).

T#1: 6. Considérese un algoritmo de 2 pasos. En el primero, se ordena la lista de manera descendiente. En el segundo paso, seleccionar el entero más grande en n y quitarlo de la lista, llamamos a este entero a. Luego declarar una variable b tal como b=y-x_i..

Utilizar una búsqueda binaria para buscar el mayor número c en la lista n tal como c=b.>_j y a como un posible valor de x_i . Es decir, se ha encontrado un par de enteros x_i y x_j tal como x_i+x_j=y.>_i+x_j porque pueden existir otras parejas que suman otro valor mayor.

Para maximizar x_i+x_j, se debe repetir el segundo paso con el nuevo entero más grande que el valor de a, hasta que la listan quede con menos de 2 elementos. Si para cualquier valor de a ningún valor de c existe, entonces seguir repitiendo el segundo paso.

El primer paso puede ser hecho en O(nlogn) usando un algoritmo de búsqueda como Merge Sort. En el segundo paso, en los peores de los casos necesitamos hacer una búsqueda de O(logn) por cada entero en n. Entonces, el segundo paso tiene complejidad de O(nlogn) y los 2 pasos juntos tienen complejidad de O(nlogn).

 T#2: 1. Para la solución de este problema de una manera eficiente se puede hacer uso de la estructura de datos Min-Heap, de la siguiente forma:

1) Crear una estructura Min-Heap de tamaño k+1 con los primeros k+1 elementos. Esto tomará O(k) tiempo.

2) Ir eliminando uno por uno el elemento mínimo de la estructura Heap, colocarlo en un arreglo resultante, y añadir un nuevo elemento al Heap de los elementos restantes. La eliminación y la adición de un elemento a la estructura Min-Heap tomará tiempo log k. Así que la complejidad general será:

O(k)+O((n-k)*logk)=O(nlogk)

La función sería:

Sortk(A[],n,k)

{Crea Min Heap con los primero k+1 elementos // int *hA=new int[k+1]

      for(i=0;i=k>

    hA[i]=A[i]

         MinHeap hp(hA,k+1) }

      for(i=k+1;ti=0;ti

            if(i{

                  A[i]=hp.replaceMin(arr[i]) }

else { A[ti]=hp.extractMin() } } }

T#2: 2. Se propone la siguiente descripción:Supongamos que el algoritmo utiliza m comparaciones para encontrar el i-ésimo elemento más pequeño identificado como x en un conjunto de n elementos.

Si trazamos estas m comparaciones, entonces fácilmente se podría encontrar los i-1 elementos más pequeños por transitividad. Si x>a y a>b, entonces x>b puede deducirse sin realizar realmente una comparación entre x y b. Del mismo modo, los n-i elementos más grandes se pueden encontrar también. Digamos que no podemos decidir que algún elemento e  es mayor o menor que x. Entonces se puede afirmar que el algoritmo no funciona correctamente, ya que se podría diseñar una entrada en la que e es el i-ésimo elemento más grande en lugar de x.

T#2: 3. Considérese un algoritmo de dos pasos: En el primer paso, ordenar la lista de manera descendente. En el segundo, seleccionar el entero más grande en n y quitarlo de la lista, llamamos este entero a. Luego obtener una variable b tal como b = y – x_i. Utilizar una búsqueda binaria para buscar el mayor número c en la lista n tal como c=b.>_j, y a como un posible x_i. Es decir, hemos encontrado un par de enteros x_i y x_j tal que x_i+x_j=y.>_i+x_j porque pueden existir otras parejas que suman otro valor mayor. Para maximizar x_i+x_j, repetir el segundo paso con el nuevo entero más grande de la variable a, hasta que la lista n quede con menos de dos elementos. Si para cualquier valor de a no existe c, entonces seguir repitiendo el segundo paso. El primer paso se puede hacer en O(nlogn) usando un algoritmo de ordenación como Merge Sort. Para el segundo paso, en el peor de los casos necesitamos hacer una búsqueda de O(logn) por cada entero en n. Entonces el segundo paso tiene complejidad de O(nlogn). Y los dos pasos juntos tienen complejidad O(nlogn).

T#2: 4. Se propone el siguiente algoritmo. (1). Crear un arreglo de salida de tamaño n*k. (2). Crear una estructura Min-Heap de tamaño k e insertar el primer elemento en todos los arreglos dentro del Heap.

(3). Repetir los siguientes pasos n*k veces:

a) Obtener el elemento mínimo del heap (el mínimo siempre se encuentra en la raiz) y almacenarlo en el arreglo de salida.

b) Reemplazar la raíz del heap con el siguiente elemento del arreglo, del cual el elemento ha sido extraido. Si el arreglo no tiene más elementos, entonces reemplazar la raíz con valor infinito. Después aplicar “heapify” al árbol. (heapify)-> Proceso de convertir un árbol binario a una estructura Heap).

• El paso importante sucede en el tercer paso, el ciclo ejecuta en n*k veces. En cada iteración del ciclo, se puede llamar la operación “heapify” en O(logk) tiempo. Por lo tanto, el tiempo total es O(nlogk).

T#2: 5. Se propone el algoritmo:Sean A[1..n] y B[1…n] 2 arreglos ordeandos, obtener el k-esimo elemento (la mediana) cuando AUB y k=n. Para esto se propone:

EncuentraKelemento(A,B,tamA,tamB,k){

Si tamA>tamB, entonces:  =>(El tamaño del arreglo A siempre debe ser menor a B)

            Intercambia Arreglos A y B

            EncuentraKelemento(B,A,tamB,tamA,k)

Si tamA=0 y tamB>0

            Regresa el valor de B[k-1]

Si k==1 => (Caso base regresa el mínimo elemento de AUB)

            Regresa el valor min(A[0],B[0])

(En este punto de aplica la técnica de “Divide y vencerás” con el fin de ir dividiendo los arreglos en k/2 para ir segmenetando el problema en arreglos más pequeños)

i=minimo(tamA,k/2)

j=minimo(tamB,k/2)

Si A[i-1]>B[j-1]

            Llama recursivamente la función:

            Encuentrakelemento(A,B+j,i,(tamB-j),k-j)

De lo contrario

            Llama recursivamente la función:

            Encuentrakelemento(A+i,B,i,(tamA-i),k-i)

}

• Al ir segmentando los arreglos en k/2 con la técnica de divide y vencerás, es ir llamando la función de manera recursiva, el algoritmo alcanza una complejidad O(logn) cuando k=n.

T#2: 6. a) Para la solución de este inciso se propone el siguiente algoritmo:

1. Inicial = 1 // 2. Final =n

3. Mientras Inicial

            med=(Inicial + Final)/2

            Si (X[med-1][med])>

                        Inicial=X[med+1]

            Si(X[med-1]>X[med]) && (X[med]>X[med+1])

                        Final=X[med-1]

            Si (X[med-1]X[med+1])[med])>

                        Return med

4. Si no se encontró al Return, entonces k es el valor de Inicial. // El algoritmo es correcto dado que hace una búsqueda binaria sobre A, verificando en cada paso si el punto medio está en la parte incremental, en la parte decremental, o si es un máximo. Nótese que si A tiene las características descritas, A tiene un máximo. // Dado que no se sabe si A[k]A[k+1][k+1]>

Caso 1: A[k][k+1]>A[1]…A[k+2]>…>A[n][k+1]>

  •A[k+1] es un máximo, además k+1 tiene las propiedades descritas

Caso 2: A[k]>A[k+1] // A[1]…A[k+1]>…>A[n]

  •En este caso A[k] es un máximo y cumple las propiedades.

De lo anterior, se cumple que es suficiente encontrar al máximo. El algoritmo encuentra al máximo, dado que si se encuentra en la parte incremental, descarta a los anteriores (que también están en la parte incremental). Si se encuentra en la parte decremental, descarta a los siguientes (que también están en la parte decremental). Si tanto el siguiente como el anterior son menores, entonces estamos con el máximo y no se debe seguir buscando. El algoritmo es de O(logn) ya que es una búsqueda binaria sobre A que realiza O(1) operaciones en cada iteración de la búsqueda.

T#2: 6(Continuación) b) Para resolver este inciso primero se encuentra n de la siguiente manera:

1. Pant=1 // 2. Psig=2

3. Mientras (Pant+1

            Si (A[Psig] ∈ A(Psig no se pasa del rango de A))

                        Pant=Psig

                        Psig=Psig*2

            En otro caso:

                        Pmed=(Psig+Pant)/2

            Si(A[Pmed] ∈ A)

                        Pant=Pmed

            En otro caso

                        Psig=Pmed

4. Return Pant

En este algoritmo para encontrar n es correcto ya que Psig al duplicarse siempre eventualmente se saldrá del arreglo. Pant por otro lado siempre estará en el arreglo y Pant =Psig/2 si es la primera vez que Psig se sale. Se hace una búsqueda binaria entre Pant y psig para encontrar el primer momento en que sale del arreglo, es decir, a la n.

Este algoritmo encuentra n en O(logn) ya que Psig se sale en O(logn) pasos dado que Pant no se sale; Pant

• Psig =2n:>

Lo que sigue es buscar a n en una búsqueda binaria en un arreglo de O(n) elementos

• Esto es de O(logn), por lo tanto, encontrar a n es de O(logn).

Posteriormente, se aplica el algoritmo del inciso a) para encontrar el máximo en O(logn). Por lo tanto, en total es de O(logn).

T#2: 7. Primero se encuentra al primer elemento de la siguiente forma:

1. Inicio=1 // 2. Final=n // 3. med =(n+1)/2

4. Mientras (Inicio

            Si(A[med]

                        Final=med

            En otro caso:

                        Inicio=med

            Med=(Inicio+Final)/2

5. Inicio tiene el valor del primer elemento de A.

6. Return (Inicio + k-1)%n

Nótese que el algoritmo es correcto ya que si Inicio>Final, entonces el subarreglo se encuentra rotado y, por lo tanto, el primer elemento debe estar en dicho subarreglo. Por otro lado, si el subarreglo no está rotado, la otra mitad si debe estar rotado. Una vez encontrado el Inicial, el k está k-1 lugares después, dado que el arreglo está rotado, se debe obtener (Inicial+k-1) % n para encontrar al que se encuentra k-1 lugares después. El algoritmo es de O(logn) ya que es una búsqueda binaria y después una operación de O(1), cada una de las instrucciones dentro de la búsqueda es O(1). La complejidad total es de O(logn).

T#2: 9. Permutaciones de Josephus.

a)  Para este caso se puede utilizar una lista doblemente ligada (lista circular) en donde cada elemento tiene 2 campos; Llave (Key) y Next. En primer lugar, hay que inicializar la lista con las Llaves(key) desde 1,2,3..,n. Esta inicialización toma un tiempo O(n). Y para que la lista sea circular el último elemento de la lista debe apuntar al primer elemento de la lista.

T#2: 9.(Continuación)

b) Para este inciso, utilizaremos un caso especial de árbol de rangos (order static tree) debido a que soporta operaciones de selección (i): encuentra el i-ésimo elemento almacenado en el árbol y rango(x): encuentra el rango de un elemento x en el árbol. Supongamos que nos ubicamos en un lugar en particular dentro de la permutación, y decimos que ese elemento es la j-ésima persona más lejana. Y resta k=n>

PermutacionJosephus(n,m){

            Inicializa el árbol T en vacio

            Desde j=1 hasta n

                        Se crea un nodo X con la key(x)=j

                        Inserta en el árbol (T,x)

            k=n,j=m

            Mientras k>2

                        Hacemos Selecciona(raíz[T],j)=> x;

                        Imprime key[x];

                        Borra del árbol (T,x)

                        k=k-1

                        j=((j+m-2)mod k)+1

            Imprime key[Selecciona(raíz[T],1)]}

• Construir un árbol de rangos toma O(nlogn) y hacer distintas operaciones en el árbol consume O(logn) de manera individual, y ejecutar todas lleva O(logn). Por lo tanto, el tiempo total del algoritmo toma tiempo O(nlogn).