STL string::find - complexity O(?)

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?

Quote:

---

Originally Posted by überfuzz

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?

---

Ah I get it, it is wrong. The log n complexity is for binary trees. An average complexity for a string search like the one I proposed the complexity is O(n/2).

Yeah except that you drop the /2 when talking about Big-Oh notation.

Ops, I shouldn't post when I'm drunk. Sorry!

I've made that mistake a few times. I would rather post while drunk then wake up to a mess I coded the night before while drunk.

Or, you know, you could stop getting drunk in the first place!

Yes, mom.