Source code online books for professionals by professionals

Forgetting. Of course, the assert doesn’t work. (
http://xkcd.com/379
)
Note
 
■
  exactly how you encode your problems and solutions as bit patterns usually has little effect on the asymptotic 
running time, as long as you are reasonable. For example, avoid representing your numbers in the unary number system 
(1=1, 2=11, 3=111…).
The asymptotic notation consists of a bunch of operators, written as Greek letters. The most important ones,  
and the only ones we’ll be using, are O (originally an omicron but now usually called “Big Oh”), W (omega), and  
Q (theta). The definition for the O operator can be used as a foundation for the other two. The expression O(g), for 
some function g(n), represents a set of functions, and a function f(n) is in this set if it satisfies the following condition: 
There exists a natural number n
0
 and a positive constant c such that
f(n) £ cg(n)
for all n ³ n
0
. In other words, if we’re allowed to tweak the constant c (for example, by running the algorithms on 
machines of different speeds), the function g will eventually (that is, at n
0
) grow bigger than f. See Figure 
2-1
 for an 
example.

---

Chapter 2 
■
 the BasiCs
13
This is a fairly straightforward and understandable definition, although it may seem a bit foreign at first. Basically, 
O(g) is the set of functions that do not grow faster than g. For example, the function n
2
 is in the set O(n
2
), or, in set 
notation, n
2
 
∈ O(n
2
). We often simply say that n
2
 is O(n
2
).
The fact that n
2
 does not grow faster than itself is not particularly interesting. More useful, perhaps, is the fact that 
neither 2.4n
2
 + 7 nor the linear function n does. That is, we have both
2.4n
2
 + 7 ∈ O(n
2
)
and
n 
∈ O(n
2
).
The first example shows us that we are now able to represent a function without all its bells and whistles; we can 
drop the 2.4 and the 7 and simply express the function as O(n
2
), which gives us just the information we need. The 
second shows us that O can be used to express loose limits as well: Any function that is better (that is, doesn’t grow 
faster) than g can be found in O(g).
How does this relate to our original example? Well, the thing is, even though we can’t be sure of the details 
(after all, they depend on both the Python version and the hardware you’re using), we can describe the operations 
asymptotically: The running time of appending n numbers to a Python list is O(n), while inserting n numbers at its 
beginning is O(n
2
).
The other two, W and Q, are just variations of O. W is its complete opposite: A function f is in W(g) if it satisfies the 
following condition: There exists a natural number n
0
 and a positive constant c such that
f(n) ³ cg(n)
for all n ³ n
0
. So, where O forms a so-called asymptotic upper bound, W forms an asymptotic lower bound.
Note
 
■
  Our first two asymptotic operators, O and 
W, are each other’s inverses: if f is O(g), then g is W(f ). exercise 2-3 
asks you to show this.
The sets formed by Q are simply intersections of the other two, that is, Q(g) = O(g) 
∩ W(g). In other words, a function f is 
in Q(g) if it satisfies the following condition: There exists a natural number n
0
 and two positive constants c
1
 and c
2
 such that
c
1
g(n) £ f(n) £ c
2
g(n)
for all n ³ n
0
. This means that f and g have the same asymptotic growth. For example, 3n
2
 + 2 is Q(n
2
), but we could just 
as well write that n
2
 is Q(3n
2
 + 2). By supplying an upper bound and a lower bound at the same time, the Q operator is 
the most informative of the three, and I will use it when possible.
cn