Summary Construct a program that computes the asymptotic complexity of an algorithm.

Learning Objectives Compute the complexity of three different algorithms using an array.

Description Using C++, build a program that displays an approximation of an algorithms asymptotic complexity, using Big O notation. The program must include a class and a driver program as described below. Use the technique of counting assignment and comparison statements as the method for computing asymptotic complexity of an algorithm. Note that this isnt the most accurate technique, but its good enough for our purposes. This assignment will be able to compute complexities that are constant, linear, or exponential. It will not work as outlined for logarithmic complexities.

File 1: BigOCalculator Class The BigOCalculator class must contain the following: Data members / fields: 1. integer to store the number of comparison statements. 2. integer to store the number of assignment statements. Functions / methods: 1. setter function / method for each of the above integers that takes one int argument. 2. getter function / method for each of the above integers that returns one int argument. 3. getBigO function / method as described below.

getBigO Function / Method Requirements - argument: one integer representing n. - return value: an integer (will be used in the driver to represent an exponent) As mentioned above, this function will work for constant, linear, or exponential complexities. To denote asymptotic complexity, we use Big O notation: - Constant: O(n0) which is equal to 1 - Linear: O(n1) which is equal to n - Exponential: O(n to some power greater than 1) So, this function needs to know the value of n, which is how many items are in the data set. Then it will compute the exponent, using the following general formula: log10 (count of comparisons + count of assignments) divided by log10 (n) The result of this calculation must then be rounded to the nearest integer. This value is what is returned to the calling code. Dont print here! The code you will need to perform this calculation is below: (int) floor ( log10 ( count of comparisons + count of assignments ) / log10 ( n ) ); Note that in C++, you must include the math.h library in order to use the floor() function.

File 2: LoopDriver Class / Program with Array Size of 10 The LoopDriver class / program is the driver for this program. This is where main will be located. You can add other functions or methods if you like or put everything in main. Create an array of size 10. You dont need to add values to the array, but you can if you want to. Instantiate one BigOCalculator object. Then add three separate types of example code (as described below) and compute the asymptotic complexity of each. For each type of example code, locate each assignment and comparison statements, and use BigOCalculators setter and getter function / methods to update the appropriate BigOCalculator variable, as each statement is encountered. Dont count them yourself and pass that number to BigOCalculator! Example statement: bigoObject.setComparisons ( bigoObject.getComparisons() + 1 ) After each example section of code is complete, display: - The number of assignments - The number of comparisons - The sum of the number of assignments + the number of comparisons - The asymptotic complexity, using the following format: "Asymptotic complexity is O(n^exponent) Note 1 The display of asymptotic complexity. Note that the ^ is the commonly accepted format for indicating the next value should be interpreted as an exponent when the font does not support superscripts. It is the character located on the 6 key in the top row on standard keyboards. So, n^2 means n2. The exponent in the above example is the return value from getBigO. n is the number of items in the array. Note 2 Dont forget to reset the number of operations. Note that after each code example, you will have to reset the number of comparisons and assignments back to 0 in the BigOCalculator object. Example Code #1 Constant Add code that compares the first and second items in the array and prints the larger value. Do not put this in a loop! The asymptotic complexity should be O(n0) which is equal to 1. Example Code #2 Linear Add a single loop to your code, similar to slide 23 of the chapter 2 slides. The asymptotic complexity should be O(n1) which is equal to n. Example Code #3 Exponential Add a nested loop to your code, similar slide 81 of the chapter 2 slides. You dont need to print the sum. The asymptotic complexity should be O(n2).