Question

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-m form. Show your work! "The runtime of foo() is e(< something >)" is not sufficient even if <something> 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<n; i++) { if(i==limit) { for(j=0; j<limit; j++) { x++; } limit = limit * 2; return x; int bar (int n) { int i, j, limit, x; limit = 16; x = 0; for(i=0; i<n; i++) { if(i==limit) { for(j=0; j<limit; j++) { x++; } limit = limit + 8; } return x;

Answer 1

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-m form. Show your work! "The runtime of foo() is e(< something >)" is not sufficient even if <something> 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<n; i++) { if(i==limit) { for(j=0; j<limit; j++) { x++; } limit = limit * 2; return x; int bar (int n) { int i, j, limit, x; limit = 16; x = 0; for(i=0; i<n; i++) { if(i==limit) { for(j=0; j<limit; j++) { x++; } limit = limit + 8; } return x;