Due: Thursday, 23 September 2021 by 10:30pm
Summary: In this assignment, you will explore some issues related to asymptotic analysis and recurrence relations.
Purpose: To enhance your understanding of how to solve recurrence relations. To give you practice with the recurrence formula theorem and proof by induction.
Collaboration (written): You may discuss this assignment with anyone you like, provided you credit such discussion when you submit the assignment. You will find that you learn the material better more if you follow initial design discussions in a group with individual writing. Each person should write up his, her, zir, or their own work and submit it individually.
Submitting: Turn in your work on Gradescope. While I would prefer that you use LaTeX, you may certainly do your work by hand. Make sure to include your name, course information, and date at the top of the page.
Evaluation: We will primarily evaluate your work on its correctness (e.g., does it compute what it is supposed to; does it meet the requirements of the assignment) and clarity (e.g., is it easy to read, is it well formatted and documented). These criteria will be modified, as appropriate, for written and coding assignments.
Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.
Consider the following recurrence relations.
Analyze a, b, and c using (i) the bottom-up approach, (ii) the top-down approach, and (iii) recurrence trees. It’s fine if you don’t find a formula based on the bottom-up approach; we just want to see you do a few examples.
Find bounds for each of the recurrences above by using the recurrence formula.
Prove the bounds of a and b using induction on n.