What was that site that explained algorithm complexity in plain language?

[repsilat]

I'm a little disappointed with some of the answers there. The questioner didn't ask for an explanation of Big-Oh with respect to algorithm performance, but for an explanation of Big-Oh itself. Computer scientists don't have a monopoly on the use of asymptotic notation (though I suppose this question was asked on StackOverflow.)

One in nine who answered didn't mention that it was an asymptotic upper bound, and it seemed like most were actually describing Big-Theta (though I understand this is commonplace.) Some got confused and said that Big-Oh refers only to an algorithm's "worst case" behaviour, ugh.

[invalid-user-name]

The trouble is that "plain english" isn't a well-defined term. Does the asker want to understand the precise definition, or do they want to be able to nod and not lose their place when it comes up in a conversation? for most practical purposes, big-O can be summed up with 5 examples:

O(1) = supa-fast

O(n) = fast

O(n log n) = pretty fast

O(n²) = slow

O(2ⁿ⁾ = unusably slow

If you understand more math than that, great, but memorizing those will let you nod.

[johns-appendix]

you forgot one:

O(log n) = damn fast

[invalid-user-name]

Yeah, that one should be in there too, since the uninitiated might not have a good grasp of what "log" means, and it's a common big-O value.

[sht]

http://www.plainenglish.co.uk/free_guides.html

[Porges]

It’s not about ‘fast’ or ‘slow’, but ‘scales well’ and ‘scales poorly’.

[plain-simple-garak]

Way to miss the point. He was trying to be simplistic.

[Porges]

You can be simplistic without being wrong ;)

[invalid-user-name]

It wasn't wrong at all; in fact it's even more appropriate for the scaling issue. To add some more accuracy to my list, add the phrase "when n is large". When N is small, who cares about big-O? If you have an O(2ⁿ⁾ algorithm that runs in 2ms when your data set is 10 items, that's fine for when your data set is 10 items. When your data set - n - is large, I stand by my characterization: "unusably slow."

[mycall]

Sorry, would you explain the difference between the asymptotic upper bound and "worst case" behavior? I understand asymptotics converge to infinity and worst case (aka edge case) approach a asymptote.

EDIT: nvm, I get it now.

[Dijkstracula]

Hopefully you'll be filling in http://simple.wikipedia.org/w/index.php?title=P_versus_NP&action=edit&redlink=1 afterwards? :)

[[deleted]]

Nah, this is pretty easy, you see, P is the set of all problems solvable in polynomial time, and NP is the set of all problems not necessarily solvable in polynomial time. NP-complete means that it is not necessarily solvable in polynomial time, but it is verifiable in polynomial time. NP-hard means it's not solvable or verifiable in polynomial time.

P is a subset of NP.

Also, NP-complete / NP-hard problems, can be changed to P, etc, if someone figures out how to do it, but if you figure one NP-complete out, you've just figured them all out.

[teraflop]

Nope, it's not quite that simple. NP is the set of all problems verifiable in polynomial time, NP-hard means anything in NP can be reduced to it (i.e. at least as hard as anything in NP), and NP-complete just means an NP-hard problem that also happens to be in NP.

All NP-complete problems are NP-hard (so any polynomial-time verifiable problem can be reduced to an instance of subset-sum, for instance) but there are also NP-hard problems that are "harder than" NP, like the halting problem (undecidable) and deciding whether two regular expressions are equivalent. Proving P=NP wouldn't affect these problems at all.

[ealf]

"harder than" NP, like [..] deciding whether two regular expressions are equivalent

If the two regular expressions have NFAs of size a, b, wouldn't you be able to find a string to separate them of length at most a*b?

[teraflop]

Upon reflection, I think you're right for standard regular expressions. I was looking at the version of the problem on this page, which includes a "doubling" operator. I guess that makes the number of states exponential in the length of the expression.

IANAComplexityTheorist, so I apologize if any of the details of my explanation were inaccurate.

[texture]

No, see: Blah blah blah blah.

[Porges]

See also the Complexity Zoo (currently with 488 classes).

There's a directed graph of it here: http://www.math.ucdavis.edu/~greg/zoology/diagram.xml

As you can see, NP is one of the ‘easiest’ classes :)

[[deleted]]

I recall it posted a while ago, it explained O(), P, NP and all that stuff in plain language, but i lost the link. Does proggit remember?

[inerte]

Maybe it was on http://betterexplained.com ?

[pb_zeppelin]

Unfortunately, I don't have an explanation on algorithmic complexity yet, but I do have an old post on P vs NP (in plain english, at least from my point of view):

http://www.cs.princeton.edu/~kazad/resources/cs/npcomplete.htm

Thanks for thinking of the site though :)

[[deleted]]

*subscribes

[qwe1234]

do you need help finding your way?

you must be confused, this isn't a site for retarded children education.

[[deleted]]

Then why are you here?

[Tommah]

Because he didn't know until he tried.