Question

PROBLEM 1 (24 points): For each of the recursive functions below and on the next page, give a correct recurrence relation expressing its runtime and then a tight runtime bound for the recurrence relation. Functions that take parameters lo and hi: n=hi-lo+1 RECURRENCE RELATION: int foo(int a[], int lo, int hi) { int x, i, j, m; X = 0; if(lo==hi) return a[10]; for(i=lo; i<=hi; i++) { for(j=i+1; j<=hi; j++) { if(a[i] % 2) x += a[i]; else x -= a[j]; TIGHT RUNTIME BOUND (-bound) m = (lo+hi)/2; return x + foo(a, lo, m) + foo(a, m+1, hi); RECURRENCE RELATION: int bar(int a[], int lo, int hi) { int x, i, m, n; X= 0: if(lo==hi) return a[lo]; n = hi-lo+1; for(i=1; i<n; i = 1*2) { x += a[lo+i]%2; TIGHT RUNTIME BOUND (-bound) m = (lo+hi)/2; return x + foo(a, lo, n) + foo(a, n+1, hi); RECURRENCE RELATION: bool goo(unsigned int a[], int n, int x) { bool resulti, result2; if(x==0) return true; if(x < 0) return false; TIGHT RUNTIME BOUND (-bound) resulti - goo(a, n-1, x); result2 = goo(a, n-1, X-a[n-1]); return resulti || result2;

Answer 1

1)

T(n) = 2T(1/2) + (nº)

using masters theorem

plog2² < n²

T(n) = P(n)

2)

T(n) = 2T(n^2) + (n)

n log22 =n

Tn) = (nlogn)

3)

T(n) = 2T(m - 1) + C - constant

by substitution method

T(n) = (27)