For each of the following functions, determine their best (lowest) worst case big-O complexity as a function of n:
def f1(n):
c = 0
step = n
while step>1:
step/=2
c++
return c def f2(n):
int c = 0
for i in range(n):
for j in range(n):
for k in range(10):
c++
return c def f3(n):
c = 0
for i in range(n):
int s = n
while(s>1):
s/=2
c++
return c def f4(n):
c = 0
for i in range(n):
for j in range(i):
c++
for k in range(n):
c++
return c def f5(n):
if n is 0:
return 1
return 1 + f5(n-1) + f5(n-1) def f6(n):
if n is 0:
return 1
c = 0
for i in range(n):
c = c + f6(i)
return c def insertion_sort(array):
for i in range(1, len(array)):
temp = array[i]
position = i
while position > 0 and array[position-1] > temp:
array[position] = array[position-1]
position-=1
array[position]=temp def bubble_sort(array):
for passes in range(len(array)-1, 0, -1):
for i in range(passes):
if array[i]>array[i+1]:
array[i],array[i+1] = array[i+1],array[i] def merge_sort(array):
if len(array) == 1:
return array
mid = len(array)//2
left = merge_sort(array[:mid])
right = merge_sort(array[mid:])
result = []
while (0 < len(left)) and (0 < len(right)):
if left[0] > right[0]:
result.append(right[0])
right.pop(0)
else:
result.append(left[0])
left.pop(0)
return result + y + z # For any elements left over