CPSC 2430 Data Structure

Winter Quarter 2022

Lab 2 Due: 11:59pm, Jan 24

Lab 2 focuses on time recursion design and complexity analysis and. In this lab, you will rewrite your Lab 1 program in a recursive approach and compare the time complexity between different implementations and explain what causes the difference using Big O notation.

Task 2: Compare the execution time between your newly implemented recursive bico() and the old bico() you implemented in Lab 1. There are multiple ways to measure your program execution time. For example, time library chrono.

// include chrono library and using its own namespace

#include

using namespace std::chrono;

// set a clock before the program executes

auto start = high_resolution_clock::now();

// program execution

//

// set a clock after the program executes

auto stop = high_resolution_clock::now();

// get the execution time by calculating the difference between two clocks

auto duration = duration_cast(stop start);

// output the duration

cout<< duration.count() << endl;

Using different input size to test two different approaches. For example, suppose your old bico() in Lab 1 is old_bico(int degree, int index), and your new recursive bico is new_bico(int degree, int index), compare the following inputs:

Task 2.1: Will the first parameter (the degree of binomial expression) affect the execution time when the function is implemented as your Lab 1?

for example, compare the execution time when n is getting larger:

old_bico(3,2)

old_bico(10,5)

old_bico(30,15)

Task 2.2: Will the first parameter (the degree of binomial expression) affect the execution time when the function is implemented as your Lab 2?

for example, compare the execution time when n is getting larger:

new_bico(3,2)

new_bico(10,5)

new_bico(30,15)

Task 2.3: Will the implementation approach affect the execution time?

for example, compare the execution time between 2 different approaches when using the same input:

new_bico(3,2) v.s. new_bico(3,2)

new_bico(10,5) v.s. new_bico(10,5)

new_bico(30,15) v.s. new_bico(30,15)

ATTENTION: you dont have to use the parameters in the example shown above. Pick whatever parameter values that could reflect the execution time change on your machine.

Task 3: Using Big O notation to explain your testing results in Task 2.3.