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.
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 the full content.
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

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

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Recursive Function Analysis and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recursive Function Analysis and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?