I've seen different numbers of the complexity of this function. With a short string as a needle and a long string as haystack a worst case is clearly O(n) and a best (1).
My question, I've also seen O(log n), how is this complexity calculated or derived?