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