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)
   4  quadratic         O(n*n)
   5  quadratic         O(n*n)
   6  linear            O(n)
   7  log(n)            O(log n)



  best ------------------ worst

  O(1)   O(log n)  O(n)  O(n*n)