The George Washington University
School of Engineering and Applied Science
Department of Electrical Engineering and Computer Science

CSci 131 - Data Structures

Week 3 Homework

1. The sequence of pentagonal numbers is the sequence 1, 5, 12, 22 ... It is computed by taking successive sums of the arithmetic progression 1, 4, 7, 10, 13 ... For example, 1 + 4 + 7 = 12, so 12 is the third pentagonal number. Write both an iterative and a recursive function to compute pentagonal numbers.

2. Write both an iterative and a recursive function that accepts a string as a parameter and returns the reversal of the string as the result.

3. Explain why recursion can lead to highly inefficient programs when used to solve certain classes of problems.

4. Determine the big-O for execution time and memory utilization of both functions written for problem 1 and both functions written for problem 2.

5. Rank the following big-O classes from least efficient to most efficient: O(n²), O(2ⁿ), O(log n), O(1), and O(n log n).