(Mathematical expressions are simplified in this html-dokument. They should be readable enough to get the flavour.)
We show that given a $k$-character query string
and an array of $n$ strings arranged in alphabetical order,
finding a matching string or report that no such string
exists requires
O( k loglog n / loglog (4+k loglog n / log n)
character comparisons in the worst case,
which is tight.
+ k + log n)