1. Define computational complexity and describe its importance in evaluating/comparing algorithms

1. Explain the difference between empirical runtime analysis and computational complexity

1. How to determine the Big-O notation from the from T(n), the number of operations which is a function of n(the data size)?

1. [30 points]

Derive T(n) for the following iterative functions and determine Big-O

a.

def check(n):

if n%2==0:

return False

i = 3

ul = math.sqrt(n)

while i <= ul:

if n % i == 0:

return False

i += 2

return True

b.

def f1(array):

for i in range(len(array)):

item = array[i]

destination = i

while destination > 0 and array[destination - 1] > item: array[destination] = array[destination - 1] destination -= 1

array[destination] = item

1. [40 points]

Derive T(n) for the following recursive functions and determine Big-O

a.

def check4(n):

if n % 4 > 1:

return n

return check4(n/4)

b.

def quickSort(arr, start, end):

if start < end:

pivot_index = partition(arr, start, end)

quickSort(arr, start, pivot_index - 1)

quickSort(arr, pivot_index + 1, end)