# USF CS 245 - Recursive Function Analysis (76 pages)

Previewing pages*1, 2, 3, 4, 5, 36, 37, 38, 39, 40, 72, 73, 74, 75, 76*of 76 page document

**View the full content.**# Recursive Function Analysis

Previewing pages *1, 2, 3, 4, 5, 36, 37, 38, 39, 40, 72, 73, 74, 75, 76*
of
actual document.

**View the full content.**View Full Document

## Recursive Function Analysis

0 0 72 views

Lecture Notes

- Pages:
- 76
- School:
- University of San Francisco
- Course:
- Cs 245 - Data Struct & Algorithms

**Unformatted text preview: **

Data Structures and Algorithms CS245 2013S 03 Recursive Function Analysis David Galles Department of Computer Science University of San Francisco 03 0 Algorithm Analysis for i 1 i n n i for j 0 j i j sum 03 1 Algorithm Analysis for i 1 i n n i for j 0 j i j sum Running Time O n4 Executed n n times Executed n n times O 1 03 2 Algorithm Analysis for i 1 i n n i for j 0 j i j sum Exact of times sum is executed 2 n X i 1 n2 n2 1 i 2 n4 n2 2 n4 03 3 Recursive Functions long power long x long n if n 0 return 1 else return x power x n 1 03 4 Recurrence Relations T n Time required to solve a problem of size n Recurrence relations are used to determine the running time of recursive programs recurrence relations themselves are recursive T 0 time to solve problem of size 0 Base Case T n time to solve problem of size n Recursive Case 03 5 Recurrence Relations long power long x long n if n 0 return 1 else return x power x n 1 T 0 c1 for some constant c1 T n c2 T n 1 for some constant c2 03 6 Solving Recurrence Relations T 0 c1 T n T n 1 c2 If we knew T n 1 we could solve T n T n T n 1 c2 03 7 Solving Recurrence Relations T 0 c1 T n T n 1 c2 If we knew T n 1 we could solve T n T n T n 1 c2 T n 1 T n 2 c2 T n 2 c2 c2 T n 2 2c2 03 8 Solving Recurrence Relations T 0 c1 T n T n 1 c2 If we knew T n 1 we could solve T n T n T n 1 c2 T n 1 T n 2 c2 T n 2 c2 c2 T n 2 2c2 T n 2 T n 3 c2 T n 3 c2 2c2 T n 3 3c2 03 9 Solving Recurrence Relations T 0 c1 T n T n 1 c2 If we knew T n 1 we could solve T n T n T n 1 c2 T n 1 T n 2 c2 T n 2 c2 c2 T n 2 2c2 T n 2 T n 3 c2 T n 3 c2 2c2 T n 3 3c2 T n 3 T n 4 c2 T n 4 4c2 03 10 Solving Recurrence Relations T 0 c1 T n T n 1 c2 If we knew T n 1 we could solve T n T n T n 1 c2 T n 1 T n 2 c2 T n 2 c2 c2 T n 2 2c2 T n 2 T n 3 c2 T n 3 c2 2c2 T n 3

View Full Document