Hola.
Efectivamente, para poder decir que un algoritmo tiene tiempo de ejecución de peor caso Omega(f(n)) hay que considerar toda posible implementación. De lo contrario, sólo estaríamos acotando inferiormente el tiempo de ejecución asintótico de una implementación particular (cosa que eventualmente nos podría interesar también).
Al margen, en la formulación de tu pregunta, lo correcto más bien habría sido “…concluir erroneamente que es Omega(n), sin saber que hay una implementacion mejor que es O(log n)” (el tiempo de peor caso de la búsqueda lineal también es Omega(log n), solo que la cota no es ajustada)
Saludos,
Álvaro