# 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 Full Document

# Recursive Function Analysis

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

View Full Document
View Full Document

## Recursive Function Analysis

72 views

Lecture Notes

Pages:
76
School:
University of San Francisco
Course:
Cs 245 - Data Struct & Algorithms
##### Data Struct & Algorithms Documents
• 27 pages

• 3 pages

• 10 pages

• 5 pages

• 3 pages

• 3 pages

• 11 pages

• 48 pages

• 4 pages

• 13 pages

• 11 pages

• 7 pages

• 27 pages

• 18 pages

• 5 pages

• 18 pages

• 2 pages

• 31 pages

• 5 pages

• 5 pages

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

Unlocking...