Description
Problem 1 (Asymptotic Growth) Rank the following functions by nondecreasing order of growth; that is, find an arrangement g1, …, g10 of the functions satisfying g1 = O(g2), g2 = O(g3), …, g9 = O(g10). All the logs are in base 2.
n2
n
, n log(n), n!, n, n100
, 2
n
, log(n), log(n!), (log(n))!, 2
2
n
.
Problem 2 (Recurrences) Give an asymptotic tight bound for T(n) in each of the
following recurrences. Assume that T(n) is constant for n ≤ 2.
(a) T(n) = 2T(n/2) + n
3
(b) T(n) = 7T(n/2) + n
2
(c) T(n) = 2T(n/4) + √
n
(d) T(n) = T(n − 1) + n
Problem 3 (Binary Search – Python) Consider the two algorithms for binary search,
shown in Figures 1 and 2.1 Each algorithm takes a sorted list of numbers, alist,
and a number, item, and returns true if and only if item is an element of alist.
The algorithm shown in Figure 1 is iterative whereas the algorithm shown in Figure 2 is recursive.
1These algorithms are taken from the book “Problem Solving with Algorithms and Data
Structures using Python” by Miller and Ranum: http://interactivepython.org/
runestone/static/pythonds/index.html .
1
CS301, Spring 2019 Homework 1
def binarySearch(alist,item):
first = 0
last = len(alist)-1
found = False
while first<=last and not found:
midpoint = (first + last)/2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return found
Figure 1: Iterative binary search
def binarySearch(alist,item):
if len(alist) == 0:
return False
else:
midpoint = len(alist)/2
if alist[midpoint] == item:
return True
else:
if item