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 << " ";

}

}