[Inspired by a G+ post https://plus.google.com/u/0/115875830338788300419/posts/9CaQPn7Q31z ]

**Set theory notation**

If is a set, and is a member, is `x in A`

.

If and are sets:

- is
`A.intersect(B)`

- is
`A.union(B)`

- is
`A.difference(B)`

- is
`A.symmetric_difference(B)`

- is
`A.issubset(B)`

- is
`A.issuperset(B)`

**Complex numbers**

There’s a trick here: math uses and Python (like electrical engineers) uses `j`

. There’s another trick: in math, if it’s variables, it’s but if it’s numbers, it is . In Python, this would be `a+b*1j`

and `5+10j`

respectively. Note that `j`

on its own, as opposed to `1j`

, is just a variable.

Notation for complex numbers, in math and in Python, is the same as for regular numbers. In particular, remember that in math, multiplication is just juxtaposition: while in Python, it’s `a*b`

. Similarly, because Python is ASCII (mostly), is `a**b`

.

**Group operations**

If is a set of numbers, would be `sum(A)`

in Python. There are subtleties here: remember that floating point numbers are not, and specifically order matters when adding up floating point numbers. would be, in Python

res = 0 for i in range(n): res += a(i)

You could, of course, use `reduce`

. Do not use `reduce`

.

Similarly, would be, in Python

res = 1 for i in range(n): res *= a(i)

**Big-O notation**

Let’s suppose `f`

is a function of a list `l`

. Big-O notation expresses an upper bound to the number of operations in `f`

, as a function of `len(l)`

, up to a constant. So saying that `f`

is `O(g(n))`

is saying there is a constant, `c`

such that `f(l)`

takes less operations than `c*g(n)`

. Here are a few examples:

# Return first element def f(l): return l[0]

This is how `O(1)`

function looks like. It will be immediately recognizable by lack of indents, though there is a trick to it — only loop indents matter.

def f(l): if l[0]: return l[1] else: return l[2]

This is still `O(1)`

.

# Search through unsorted list for its first element def f(l): for i in range(1, len(l)): if l[i] == l[0]: return i

This is the typical `O(n)`

. Again, the typical one-indent says so, ignoring if indents.

# Search through sorted list for first element # (list is only sorted starting second element) def f(l): target = l[0] low = 1 high = len(l)-1 while low

Wait, what’s that? Yes, there’s one indent, but we do not loop through the numbers.

When you see a while loop with a “halve distance” functionality, that indent is only worth `log(n)`

.

Since here this is the only indent, this function is `O(log(n))`

.

# Find a common element between first half of list # and second half of list def f(l): mid = len(l) firstHalf = l[:mid] secondHalf = l[mid:] for i in range(mid): for j in range(mid): if firstHalf[i] == secondHalf[j]: return i,j+mid

This should be easy, now — two indents, `O(n**2)`

(or, in math terms, ).

# Find a common element between first half of list # and second half of list # Assume second half is sorted. def f(l): mid = len(l) firstHalf = l[:mid] secondHalf = l[mid:] for i in range(mid): low, high = 0, mid target = firstHalf[i] while low

One indent worth `n`

, the next worth `log(n)`

for a total of `O(n*log(n))`

.

Really? There are people out there who call themselves programmers who need a crash course in basic math?

I mean seriously, this is High-School level education you are describing here.

I never saw a Σ in high school. I didn’t even see a Π in college. There are definitely people who might find themselves needing this crash course. (Although mathematical notation is dumb as it is a restricted and obscure subset of what we can represent in programming languages.)

This is meant to enable reading, not writing, math. If you are reading something, you do not have a choice about the notation it uses.

I can only comment from a German perspective, but we do basic set theory in eighths grade. Of course this is most useful in college when you get involved with sequences and series, but without that basic knowledge, you’d have a hard time getting accepted into any college for a technical degree.

This only includes the math part, not the programming part. German high school education is way back when it comes to doing anything at all with computers.

This post is invaluable. So mofo, stfu and gtfo.

Why not use reduce?

Function call overhead.

For Σ the direct Python equivalent is the sum built-in function. reduce (or a for loop) is only needed for Π

Really… such a important web-site