P/NP

[smantix]

When began our discussion of P vs. NP a couple of Fridays ago, we got
onto the topic of polynomial-time and nonpolynomial-time algorithms.
That led to a fumbling explanation (mine) of "big O" notation as a way
of indicating algorithm efficiency. Brian Harvey's fifth lecture in
the Berkeley SICP series "Orders of Growth" provides a gentle, folksy
introduction to big-O and theta notation. (http://academicearth.org/
lectures/orders-of-growth) Worth a look.

If you don't have the time, he pretty much boils it down to a few
important categories:

O(n) - linear time, like a vanilla exhaustive search.
O(n^2) - quadratic time, like matrix multiplication or an inefficient
sort.
O(log n) - log-linear, like an efficient search
O(n log n) - like an efficient sort

and the ugly intractable stuff:
O(2^n)
O(n!)
O(n^n)

Actually, Harvey uses theta notation, which is new to me. I'll have to
find where that comes from.