CSS340 Program 3-Algorithm Analysis Solved

Algorithm Analysis

This assignment will focus on algorithm analysis (Big O). It will have both a written part as well as a programming part. The goal is to clearly show the impact of algorithms with different complexity.

Written Problems:

1. What is the Big O upper bound of the func() below as a function of n assuming that the Func1(n) is O(n)? Prove your answer.

   n): n

   n)

2. Determine the BigO complexity of func2() as a function of n assuming the task(a,b) is

def func(

j=

while j >= 1:

for

i in

range(j):

O(1).

val = func1(

j = j // 3

def func2(

n):
n

n)):

for

i in r
j in

ange(1,

+1):

for

range(i,1 + (i*

task(i+1,j)

3. Letkbeapositiveinteger. Showthat1k+2k+3k+…+nk isO(nk+1).

Programming Problem:

Create a module called bigo which has four functions, find1(list, val), find2(list, val), find3(list, val), and find4(list, val). Each of the functions will take as arguments a list followed by a value. The functions will return a boolean as to whether the val is a member of the list.

The specification for each of the functions is as follows:

find1(list, val): The unsorted list is searched linearly to see if the val is in the list

find2(list, val): A deep copy is made of the list; the copied list is then sorted using the sort built- in function and then a binary search is performed on the list to find if the val is in the list

find3(list, val): The in built-in is used to determine if the val is in the unsorted list
find4(list, val): This function requires the list to be sorted before it is called. A binary search is

performed on the pre-sorted list to find val.

Code the four functions in module as described above. Write a report which:

1. 1)  Determines the BigO complexity for each function
2. 2)  Graphically depicts the running time of each of the functions as the size of the list

   increases. Do this using the Timer in the python TimeIt module.