Introduction Compare the chart you created to the Big$-$O complexity chart and answer the following questions.

What do you estimate the time complexity to be$?$

Use the closest function from the chart to estimate how many operations $10$ rings would require? $100?1,000?$

Is this a practical algorithm for large input sizes? Explain your reasoning.

Big$-$O Complexity Chart

Bad Fair Good

In this lab you will find several exercises to strengthen your understanding of recursion and

C$++$ arrays. Turn in all your work $($code$,$ spreadsheets, graphs, and short answers$)$ into

Blackboard.

Part $1$: Recursion

A$.$ Write a recursive function named factorial that computes the factorial for a given

int.

B$.$ Write a recursive function named fibonacci that computes the value of the $n^{th}$

Fibonacci sequence: $1,2,3,5,$dots

C$.$ Write a function named towers that counts the number of moves in Towers of Hanoi

given the number of rings $n.$

Part $2$: Unit Testing

Write test functions for the three functions in part $1.$ Name your test functions with

a "test" prefix; for example, testRecursiveContains. Use the minimal test equivalence

class to ensure a minimal yet complete test. Use c$-$style asserts to verify and validate

values or print to the console for manual verification.

Part $3$: Time Complexity

Review Big$-$O notation in the link provided ${?}^1.$ In this exercise we'll explore the time

complexity of the recursive Towers of Hanoi solution. Below you'll see a Big$-$O complexity

chart we'll use later containing common ways algorithm operations can scale with user

input.

The towers function you created outputs the number of moves required for the

number of rings given. Use this function to gather several input and output sample points.

Enter these points into a spreadsheet program such as Google Sheets or Microsoft Excel.

Once you have a dozen or sample points, create a plot like in the Big$-$O complexity chart.