## 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