Analysis of Recursive Algorithms

Algorithms

Abstract

This activity focuses on analyzing time complexity of recursive algorithm through solving recurrence relation mathematically, including linear, logarithmic, and exponential complexity. At the end of this activity, students will compare the efficiency of different implementations of computing Fibonacci numbers using time complexity. This topic is usually a challenging new content for students who just learned time complexity analysis for non-recursive algorithms, mainly because there is a significant learning curve of summarizing and solving the recurrence relations for recursive algorithms. This activity has been used in my Algorithms class a couple of times in past few Fall semesters.

This activity was developed with NSF support through IUSE-1626765. You may request access to this activity via the following link: IntroCS-POGIL Activity Writing Program. 

• Level: Undergraduate
• Setting: Classroom
• Activity Type: Learning Cycle
• Discipline: Computer Science
• Course: Algorithms
• Keywords: recursion, algorithm analysis, factorial, Fibonacci number