Assignment 1 Spring 2024 Math Review and Algorithm Analysis

Use empirical analysis methods and code analysis methods to determine running time complexity in Big O notation.

Review of Common Math Functions.

Use Excel or some other graphing tool to graph the following

y = x y = 2x y = x² y = 2^x

y = x³

y = log₂ x

Rank the graphs of the above equations by rate of growth, fastest (non-initial) growth

Match the shape of each graph with the closest common Big(O) curve and label them

Empirical Analysis (counting and plotting the “work”).

Complete the table for each of the following functions. For each foo, write a small program with a loop where N is a counter from 0 to at least Call the foo within the loop, passing it each value of N, and getting the return value from foo. Something like this:

void main(void)

{

for (int = 0; < 50; ++)

cout << << ” ” << foo1() << endl;

}

N	return value
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
32
64

Fill out a table with each N and its corresponding return value. You can skip some values of N when N starts to get biggish. Capture your output and generate the tables. See the posted “Bsort BigO.cpp” optimization code as an example of this kind of analysis.

int foo1(int )

{

int counter = 0;

for(int i = 0; i < ; i++) counter++;

return counter;

}

int foo2(int )

{

int counter = 0;

for(int i = 0; i < ; i++) for(int j = 0; j < ; j++)

counter++;

return counter;

}

int foo3(int )

{

int counter = 0;

for(int i = ; i > 0; i = i/2) counter++;

return counter;

}

// note: you might not make it much past n = 32 int foo4(int )

{

static int counter = 0; counter++;

if( > 0)

{

foo4(-1);

}

return counter;

}

Use Excel to GRAPH the data tables from the previous Use the return value as a function of

That means, put N on the horizontal axis (x) and put the return value on the vertical axis (y). Use Excel or some other similar plotting tool.

Rank the graphs above by rate of growth, fastest

More Empirical Analysis, but with Series

Continue the process used above to test the following series Use iterative solution given, do not use the equivalent (condensed) algebraic formula given in the class notes.

I. Arithmetic Series

Test for values of N from 1 to a lot.

𝑁

∑ 𝑖 = 1 + 2 + 3+. . . +𝑁

𝑖=1

Iterative code solution:

int arithSeries(int )

{

int sum = 0;

for (int i = 1; i <= ; i++) sum = sum + i;

return sum;

}

II. Geometric Series

Test for values of N from 0 to a lot.

𝑁

∑ 2^𝑖 = 2⁰ + 2¹ + 2² + 2³+. . . +2^𝑁

𝑖=0

Iterative code solution:

int geomSeries(int )

{

int sum = 0;

for (int i = 0; i <= ; i++)

{

int term = 1;

for (int j = 0; j < i; j++) term = term * 2;

sum = sum + term;

}

return sum;

}

III. A More Efficient Geometric Series

Redo the previous solution using only a single loop instead of the nested loop. You can get rid of the inner loop if you keep a running total for term in the outer loop, instead of resetting term and recalculating it in the inner loop. If your solution has only one loop, then it should have a BigO(n) time complexity.

For the previous three series implementations, determine the BigO of each series by analysis of the source code using our Big O “rules of thumb” and by looking at the shape of the plots.

attachment_1 (1)