Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Guías prácticas/Complejidad computacional/Solución al ejercicio 1 de complejidad computacional

El primer algoritmo de búsqueda recorrerá todos los elementos del arreglo en el peor de los casos, de manera que su complejidad será de $O(n)$. El segundo –la búsqueda binaria- divide en dos el campo de búsqueda en cada llamada o iteración, de manera que, en el peor de los casos, la cantidad $p$ de pasos será tal que:

${\frac {n}{2^{p}}}\leq 1\Rightarrow 2^{p}\geq n\Rightarrow p\geq log_{2}n$ -el entero igual o inmediatamente superior a $log_{2}n$.

Si el arreglo está ordenado, evidentemente convendría utilizar el algoritmo de búsqueda binaria.

Si no está ordenado, ordenarlo costaría por lo menos un tiempo de $O(nlog(n))$, que es superior al orden de tiempo de búsqueda lineal.

Algoritmo	Encontrar el primer elemento	Encontrar el elemento en la mitad
Búsqueda lineal	O(1)	O(n)
Búsqueda binaria	$log(n)$	O(1)

Algoritmo	Mejor caso	Peor caso	Caso medio
Búsqueda lineal	Primer elemento	Elemento ausente	Elemento del medio
Búsqueda binaria	Elemento del medio	Elemento ausente	Posiciones intermedias[1]

---

^ El caso medio para el buscador binario es cualquier posición que se alcance en ${\frac {log_{2}n}{2}}$ pasos.