Randomizd String Searching
The average complexity of the search from the back to the front is equal to
$$
  \sum_{i=1}^n  \frac{2i}{n(n+1)}(n-i+1) = \frac{2}{n(n+1)}\sum_{i=1}^n i(n-i+1) = \frac{2}{n(n+1)} \frac{1}{6}n (n+1) (n+2) = \frac{1}{3}(n+2)
$$ 
which is indeed linear.