PROBLEM 1 (60 pts.): For each of the functions below, give as tight a worst-case runtime bound as you can. Express your answers with Big-O / Big-Theta notation.

Since you are seeking "tight" bounds, your answers should be expressed using Big- -- unless you are especially candid and aren't sure if your upper-bound is indeed tight, you might say something like "I know the worst case is O(), but I have not been able to show that this is a tight bound..."

• Show your reasoning and

• express your answers in the SIMPLEST TERMS POSSIBLE!!

// 7 points int A(int a[], int n) { int x=0, i, j; for(i=0; i

x += a[i]%2;

} for(i=0; i

// 8 points int C(int a[], int n) { int x=0, i, j, k; for(i=1; i

}

}

k = n;

while(k>0) { x += a[k];

k = k/2; } return x; } // 8 points int D(int a[], int n) { int x=0, i, j; for(i=0; i

} else x--; } return x; }

// 10 points int E(int a[], int n) { // tricky! int x=0, i, j; for(i=0; i