# deque vs list: performance notes

Remco Gerlich scarblac-spamtrap at pino.selwerd.nl
Wed May 31 18:11:05 CEST 2000

```Michael Hudson wrote in comp.lang.python:
> david_ullrich at my-deja.com writes:
>
> >      You sure about that "n!"? Seems more like n^2 to me.
> > (Of course n^2 is big, but n! would be much worse. It's
> > a theorem that n! is bigger than anything.)
>
> n^n is worse than n!, if you're after really bad algorithmic
> performance.

There exists some mathematical proof, by Ronald L. Graham, about an upper
this is from some web page I saved once). It uses a rather large number.

Really large numbers come in Knuth notation, like 3^3 or 3^^7 or 7^^^4.
Defined by the following Python function:

def knuth(num, power, arrownum):
if not arrownum:
return num*power
for i in range(power-1):

So 2^4 = 2 ** 4 = 16.

3^^4 = 3^(3^(3^3))

7^^^3 = 7^^(7^^7)

3^3 = 3*3*3 = 27. Easy.

3^^3 = 3^(3^3) = 3^27 = 7,625,597,484,987. "So small I can actually type it".
Still a number you can visualize somewhat, ie the gross national product.

3^^^3 = 3^^(3^^3) = 3^3^3^3^3^3^3^3^3^.....^3^3 (7 trillion threes).
Too big to understand. After the first few terms you're already far above
small numbers like the number of particles in the universe. But at least you
can store that expression (3^3^3^3...) in eight terabytes of memory.

3^^^^3 = 3^^^(3^^^3) = 3^^(3^^(3^^(3^^..... (repeat by the amount of the
previous number...)))).
There are no words for this number.

To get Graham's number, you take x = 3^^^^3. Next, you set x to 3^^^...(x
^'s)...^^^3. Repeat 63 times.

x = 4
for i in range(64):
x = knuth(3,3,x)

Now *that's* a large number.

Of course, most finite numbers are much larger than that ;-).