Relación de recurrencia del número de comparaciones en búsqueda binaria - algoritmo, búsqueda binaria, recurrencia

Tengo dudas sobre la relación de recurrencia para el número de comparaciones en la búsqueda binaria.

Leí que recurrence se puede escribir como T (n) = T (n / 2) + 1 en este sitio web http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L14-RecRel.htm

Según mi opinión, debería ser T (n) = T (n / 2) + 2, ya que en el peor de los casos el elemento podría no estar presente en la matriz y terminaremos haciendo 2 comparaciones en cada pasada.

Por favor dime si tengo razón o no.

Respuestas

Creo que tienes razón.

EN MI HUMILDE OPINIÓN, compare a b significa que sabemos a=b, a>b o a<b al mismo tiempo. Es decir, 1 comparación puede tener 3 resultados diferentes.

Pero para lenguajes de programación. Tenemos que usar 2 comparaciones.

if mid == x:      found it!          # 1st
else if mid < x:  search right       # 2nd
else:             search left

Te refieres a la == y < son 2 comparaciones.

Sin embargo, no afecta el resultado. Porque usamos una notación O grande para representar la complejidad. Es solo una cuestión de constante, pero O por lo general no le importa.

De acuerdo a teorema maestro. Ya sea +1 o +2 dará como resultado la misma complejidad O(log n).

Lo que queremos suele ser un límite (Big-O), no es un resultado preciso de ecuación matemática.

Creo que lo que importa aquí es que 1 y 2 ambos son tiempo constante. También podemos dividir ==, > en las instrucciones de la máquina, y puede ser mayor que 2. O tal vez algunos lenguajes de programación o CPU utilizan la comparación, solo cuesta 1 comparación. Pero no importa aquí al hacer un análisis asintótico.

1. https://en.wikipedia.org/wiki/Master_theorem
2. https://en.wikipedia.org/wiki/Asymptotic_analysis