[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:
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
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
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
Similarly, would be, in Python
res = 1 for i in range(n): res *= a(i)
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
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
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: return l else: return l
This is still
# Search through unsorted list for its first element def f(l): for i in range(1, len(l)): if l[i] == l: 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 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
Since here this is the only indent, this function is
# 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