Crash course in mathematical notation for programmers

[Inspired by a G+ post ]

Set theory notation

If A is a set, and x is a member, x \in A is x in A.

If A and B are sets:

  • A \cap B is A.intersect(B)
  • A \cup B is A.union(B)
  • A \backslash B is A.difference(B)
  • A \triangle B is A.symmetric_difference(B)
  • A \subset B is A.issubset(B)
  • A \supset B is A.issuperset(B)

Complex numbers

There’s a trick here: math uses i and Python (like electrical engineers) uses j. There’s another trick: in math, if it’s variables, it’s a+ib but if it’s numbers, it is 5+10i. 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: ab while in Python, it’s a*b. Similarly, because Python is ASCII (mostly), a^b is a**b.

Group operations

If A is a set of numbers, \Sigma A 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. \Sigma_{i=0}^n a_i 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, \Pi_{i=0}^n a_i 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]
        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, O(n^2)).

# 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)).


9 Responses to Crash course in mathematical notation for programmers

  1. Marcus says:

    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.

    • glyph says:

      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.)

      • moshez says:

        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.

      • Peter says:

        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.

    • bigO says:

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

  2. glyph says:

    Why not use reduce?

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

  4. Really… such a important web-site

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: