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

PROBLEM 2 (30 pts.):

Analyze the runtime of C functions below and give a tight runtime bound for each.

• Both functions have the same best-case and worst-case runtime (so this is not an issue).

• Since we want a "tight" runtime bound, your final answer should be in big- form.

• Show your work! "The runtime of foo() is ()" is not sufficient even if happens to be correct. In other words, convince the reader of the correctness of your answer.

int foo(int n) {

int i, j, limit, x;

limit = 16;

x = 0;

for(i=0; i

if(i==limit) {

for(j=0; j

x++;

}

limit = limit * 2;

}

}

return x;

}

int bar(int n) {

int i, j, limit, x;

limit = 16;

x = 0;

for(i=0; i

if(i==limit) {

for(j=0; j

x++;

}

limit = limit + 8;

}

}

return x;

}

PROBLEM 3 (20 pts.):

The function below distributes jelly beans to n children. Analyze the code and answer the question to the right.

Analyze the function and a tight worst-case runtime bound for it (you are looking for a big- bound).

Apply the same guidelines as in the previous problems.

void jelly(int a[], int n) {

int i, j;

int beans=10*n;

// all children start with

// zero beans.

for(i=0; i

a[i]=0;

// hand out beans one by one

// to a random child

while(beans > 0){

i = rand() % n;

a[i]++;

beans--;

}

// print one line of beans

// for each child

for(i=0; i

cout << "CHILD " << i << ": ";

for(j=0; j

cout << "bean! ";

cout << " ";

}

}