Comment by RiderOfGiraffes | Hacker News Reader

Comment by RiderOfGiraffes | Hacker News Reader

RiderOfGiraffes

You don't really want to know the full complexity zoo (look it up) really you don't. You want to know the difference in the practical sense between

* 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?

I'll bite on the last one. How can string search be sublinear? Boyer-Moore, the fastest algorithm I know of, is still O(n) regarding the length of the search string. Since strings are inherently linear, you'd need a transformation step to leverage the advantages of another data structure (e.g. suffix tree or a DAWG), and that transformation would need to look at each token. Am I missing somehting?

Example:

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.

Aren't you just futzing the constant, though? Sublinear doesn't mean O(Cn) where C < 1.

That's still O(n). Say you're looking for that string in a string of length n. You're search time will be n/16+c, which is O(n).

Reply on news.ycombinator.com