Preguntas etiquetadas con average-case

Estoy tratando de derivar el artículo clásico en el título solo por medios elementales (sin funciones generadoras, sin análisis complejo, sin análisis de Fourier) aunque con mucha menos precisión. En resumen, "solo" quiero demostrar que la altura promedio hnhnh_n de un árbol con nnn nodos (es...

Considerando este pseudocódigo de un bubbleort: FOR i := 0 TO arraylength(list) STEP 1 switched := false FOR j := 0 TO arraylength(list)-(i+1) STEP 1 IF list[j] > list[j + 1] THEN switch(list,j,j+1) switched := true ENDIF NEXT IF switched = false THEN break ENDIF NEXT ¿Cuáles...

¿Cómo demuestra que la altura esperada de un árbol de búsqueda binario construido aleatoriamente con nnn nodos es O(logn)O(log⁡n)O(\log n) ? Hay una prueba en CLRS Introducción a los algoritmos (capítulo 12.4), pero no la