How many *steps* for each of the following?
And what happens to the number of steps when n doubles to 2n?
Try to classify each of the following as one of these:
O(logN), O(N), O(NlogN), O(N*N).

```
#############################################
# 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
#############################################
# 8
L = [1,2,5,7,13,21,24,25,26,33,34,38,50,57,58,63]
n = len(L)
mid = n/2
print L[mid]
#############################################
# 9
n = int(raw_input("n: "))
for i in range(n):
k = n
while k > 1:
print i, k
k = k/2
#############################################
```

`searches.py`

fileWrite a program called `lookup.py`

that simply asks for a word, and then
tries to find the word in the system word list (`/usr/share/dict/words`

).
Here is an example:

```
$ python lookup.py
word: hello
Found
word: pickles
Found
word: sdkjflkdjf
NOT Found
word:
```

In your program, include `from searches import *`

to import our two
search functions. If we are searching through the system word list,
which is in alphabetical order, which search function should we use?

Another way to compare algorithms is by simply timing two algorithms on the same computer with the same data. For a spell-checking program, searching about 3000 times, through the system word list (99171 words), my linear search program took about 13 seconds to run, while the same program using binary search took only 4 seconds. What would happen to each if we doubled the size of the list we are searching through?

Here is an example of using the python `time()`

function to see how
long a block of code takes to run:

```
>>> from time import time
>>> t1 = time()
>>> x = 0
>>> for i in range(1000000):
... if i%2 == 0:
... x += 1
... else:
... x += 2
...
>>> t2 = time()
>>> total = t2 - t1
>>> print(total)
9.0005819798
```

One of our students, Ben Schreiber, made a website to help students
understand and learn various searching and sorting algorithms. His website
includes a summary of binary search, an analysis of binary search, and
a coding example with **a song to help you remember the algorithm**. If you
are struggling to understand how binary search works (or the sorting
algorithms we learn next week), check out
Ben's musicAlgo.com site