# For each of the following recursive methods, write and solve a recurrence of the form

# T(n) = aT(f(n)) + g(n) # to describe its running time. Assume all initial calls have the form f(a,len(a) - 1 ) or

# f(a,0,len(a) - 1). def f1(a, n): if n > 0: for i in range(len(a)): print(a[i]) f1(a, n - 1) def f2(a, n): if n > 0: for i in range(len(a)): print(a[i]) f2(a, n // 2) def f3(a, n): if n > 0: f3(a, n // 2) def f4(a, n): if n > 0: for i in range(len(a)): print(a[i]) f4(a, n // 2) f4(a, n // 2) def f5(a, first, last): if first < last: for i in range(first, last + 1, 1): print(a[i]) mid = (first + last) // 2 f5(a, first, mid) f5(a, mid + 1, last) def f6(a, n): if n >= 0: print(a[n]) f6(a, n - 1) f6(a, n - 1) def f7(a, first, last): if first < last: print(a[first]) f7(a, first + 1, last - 1) print(a[last])

def f8(a, first, last): if first < last: for i in range(first, last + 1, 1): for j in range(first, last + 1, 1): print(a[i]) mid = (first + last) // 2 f8(a, first, mid) f8(a, mid + 1, last) def f9(a, first, last): if first < last: for i in range(first, last + 1, 1): for j in range(first, last + 1, 1): print(a[i]) mid = (first + last) // 2 for i in range(4): f9(a, mid + 1, last) def f10(a, first, last): if first < last: for i in range(first, last + 1, 1): for j in range(first, last + 1, 1): print(a[i]) mid = (first + last) // 2 for i in range(4): f10(a, first, mid) f10(a, mid + 1, last) def f11(a, n): if n > 0: f11(a, n - 1) print(a[n]) def f12(a, first, last): if first < last: for i in range(first, last + 1, 1): for j in range(first, last + 1, 1): for k in range(first, last + 1, 1): print(a[i]) mid = (first + last) // 2 for i in range(8): f12(a, first, mid)