Thanks
* logarithmic
* sub-linear
* linear
* quadratic (and other low powers)
* polynomial
* sub-exponential
* exponential
* super-exponential
* NP
* NP-Hard
* The intersection of those last two (NP-complete)
And for each - give examples.
Then you want to say, for a given algorithm, what it's complexity looks like. What's bubble-sort? Why? What's QuickSort? Best case? Worse case?
What's packing? A*? Travelling Salesman? Factoring?
What about the various database operations?
Skim the wikipedia pages on each of those, concentrating on the feel of the algorithm and the statement of the complexity. Then ask about other algorithms, and try to get a sense of how they feel. And why.
Finally - Why can string search be sub-linear?
If you're looking for "aaaaaaaaaaaaaaaa" (that's a string of length 16) and you look in index 15 (counting from 0) and find a non-"a" there, you can leap forward 15 (or 16 - there's an off-by-one error waiting to bite) places. If that's also not an "a" then you can do it again.
It's more complex than that, but the complexity can, in some cases, be sub-linear.
There's another reference I have somewhere to a surprising (and contentious) sub-linear algorithm for something that's "obviously provably linear". I'll see if I can dig it up and post it later. No time now.
ADDED IN EDIT (because there's more than one reply saying the same thing)
Yes, it's futzing the constant. The point is that the constant can be less than one, it's not always necessary to examine every character in the string being searched, which comes as a surprise. But no, this is not sub-linear, although many people describe it as such. Knowing why it's not sub-linear, even when the constant is less than one, is an important milestone in learning about complexity of functions.