Given an ordered list $$ and value $,$ the LowerBound algorithm provide the position $$ in list $$

such that $$ is the first offset in $$ of a value larger$-$equal to $.$ Hence, $<=[]($or$,$ if no such offset exists,

$=||).$ The LowerBound algorithm does so in $\backslash$Theta $($log$2$

$(||))$ comparisons.

Argue that LowerBound is worst$-$case optimal: any algorithm that finds the correct position $$ for any

inputs $$ and $$ using only comparisons will require $\backslash$Theta $($log$2$

$(||))$ comparisons