```
WEEK09: searching, analysis of algorithms
---------------------------------------------------------------
W: Quiz 4, algorithm analysis...

# How many "steps" for each of the following?
# What happens to the number of steps when n --> 2n?

#############################################
# 1
n = int(raw_input("n: "))
for i in range(n):
print i
#############################################
# 2
n = int(raw_input("n: "))
for i in range(100):
print i*n
#############################################
# 3
n = int(raw_input("n: "))
for i in range(n):
print i
for j in range(n):
print j
#############################################
# 4
n = int(raw_input("n: "))
for i in range(n):
for j in range(n):
print i, j
#############################################
# 5
n = int(raw_input("n: "))
for i in range(n):
for j in range(i,n):
print i, j
#############################################
# 6
n = int(raw_input("n: "))
for i in range(n):
for j in range(10):
print i, j
#############################################
# 7
n = int(raw_input("n: "))
while n > 1:
print n
n = n/2
#############################################

- for #7, what happens when we enter 1 million for n??

>>> n = 1000000
>>> while n > 1:
...   print n
...   n = n/2
...
1000000
500000
250000
125000
62500
31250
15625
7812
3906
1953
976
488
244
122
61
30
15
7
3

If you count that up, it's about 19 times.

Here's the mathy way to say that: log-base-2 of n

>>> from math import *
>>> log(1000000, 2)
19.931568569324174

If I double the amount of data we are using (n = 2000000),
how many additional steps the above loop take?

>>> log(2000000, 2)
20.931568569324174

JUST 1 more step than the n=1000000 case!!!

- table for above loops:

#  name             Order
1  linear            O(n)
2  constant time     O(1)
3  linear            O(n)