La probabilidad de encontrar un elemento en la primera posición de una matriz es 12, la probabilidad de encontrarlo en la última es 1/3
El elemento que buscamos está sin duda en la matriz.
Si el artículo está en el $n_{th}$ posición, entonces se necesitan n operaciones para encontrar el elemento.
Mi intento de encontrar el valor esperado de la cantidad de tiempo que se tarda por término medio en encontrar el artículo:
(1)
$p_1 = \frac{1}{2}, p_n = \frac{n}{3} , p_i = \frac{1}{6(n-2)}, 1 < i < n$
(2)
$E(n) = \frac{1}{2} + \frac{n}{3} + \frac{1}{6(n-2)} (\sum_{i=1}^{n-1} - 1) $
(3)
$E(n) = \frac{1}{2} + \frac{n}{3} + \frac{1}{6(n-2)} \frac{(n-1)n-2}{2} $
(4)
$E(n) = \frac{1}{2} + \frac{n}{3} + \frac{(n^2 - n) - 2}{12(n-2)} $
Sin embargo, parece que $\in O(n^2)$ Lo cual no tiene sentido, ya que en el peor de los casos se tarda O(n) en encontrar el elemento. ¿En qué me he equivocado?
