Csc 323: Algorithm Design And Analysis

CSC 323: Algorithm Design and Analysis Analysis Basics

Non-Recursive Algorithms • When we count operations that occur in loops, we only need to determine how many operations there are inside the loop and how many times the loop is executed. • Recall our Largest Value Algorithm. • largest = list[1] • for i = 2 to N do – if list[i] > largest then » largest = list[i] – end if

• end for

Non-Recursive Algorithms • So, our analysis of the Largest Value algorithm has given us the following results: • B(N) = 1; Best Case • A(N) = (N + 1)/2; Average Case • W(N) = N; Worst Case

• It is important to always be mindful of what operation(s) were counted for the analysis.

Recursive Algorithms • However, for recursive algorithms it is not clear how many times an operation will be done. This depends on: – Recursive Calls – Preparatory Work – Concluding Work

Recursive Algorithms • Consider the following recursive algorithm to compute the factorial of a number, N. • Factorial( N ) • if N == 1 then • return 1

• else • smaller = N – 1 • answer = Factorial( smaller ) • return (N * answer)

• end if

Recursive Algorithms • How will this algorithm compute Factorial ( 4 )? • Factorial ( 4 ) • Call Factorial ( 3 ). • Call Factorial ( 2 ). • Call Factorial ( 1 ). • Then?????

Recursive Algorithms • To analyze recursive algorithms, we use the following formula: DIR( N ), for N ≤ SizeLimit REC( N ) = DIV( N ) + ΣREC( smallerSizes[ i ] ) + COM ( N ), for N > SizeLimit

Recursive Algorithms • Thus, for our algorithm Factorial( N ), we have: 0, for N = 1

Calc( N ) = 1 + Calc( N – 1 ) + 1, for N > 1

• What operation is being used for this analysis? • What is the time complexity of this algorithm?

Recursive Algorithms • Recurrence relations can be directly derived from a recursive algorithm. • To determine the time complexity (efficiency) of the algorithm we need to convert the set of recursive algorithms into closed form by removing the recursive nature of the equations.

Recurrence Relations • A recurrence relation is a recursive form of an equation, for example: T (1)   =  3 T (n)   =  T (n − 1)  +  2

• A recurrence relation can be put into an equivalent closed form without the recursion

Recurrence Relations • Begin by looking at a series of equations with decreasing values of n: T (n)   = T (n −1)  +  2 T (n −1)   = T (n −2)  +  2 T (n −2)   = T (n −3)  +  2 T (n −3)   = T (n −4)  +  2 T (n −4)   = T (n −5)  +  2

Recurrence Relations • Now, we substitute back into the first equation: T (n)   = T (n − 1)  +  2 T (n)   = (T (n −2)  +  2)  +  2 T (n)   = ((T (n −3)  +  2)  +  2) +  2 T (n)   = (((T (n −4)  +  2)  +  2) +  2) +  2 T (n)   = ((((T (n −5)  +  2)  +  2) +  2) +  2) +  2

Recurrence Relations • We stop when we get to T(1): T (n)   =  T (n − 1)  +  2 T (n)   =  (T (n − 2)  +   2)  +  2 M T (n)   =  (L ((T (1) +   2) +   2)L  +   2) +  2

• How many “+ 2” terms are there? Notice we increase them with each substitution.

Recurrence Relations • We must have n of the “+ 2” terms because there was one at the start and we did n - 1 substitutions: n

T (n)   =  T (1)  +  ∑ 2 i= 1

• So, our closed form of the equation is: T (n)   =   3 +   2n

Suggested Exercises • Exercises 2.1.1, pg. 34 • 1–4

• Exercises 2.2.2, pg. 41 • 1 – 4 & 9 – 12

Suggested Exercises Exercises 2.1.1, #1 • int Fibonacci( N ) • if N == 1 or N == 2 then – return 1

• else – value1 = N – 1 – value2 = N – 2 – return Fibonacci( value1 ) + Fibonacci( value2 )

• endif

Suggested Exercises Exercise 2.1.1, #1 0, if N = 1 or 2 Add( N ) = 2 + Add( N – 1 ) + Add( N – 2 ) + 1, for N > 2

Suggested Exercise Exersice 2.1.1, #2 • Power( X, Y ) • if Y == 0 then – return 1

• else – value = Y – 1 – return X * Power( X, value)

• endif

Suggested Exercises Exercise 2.1.1, #2 0, if Y = 0 Mult( Y ) = 0 + Mult( Y – 1 ) + 1, for Y > 0

Suggested Exercises Exercise 2.1.1, #3 • Power( X, Y) • if Y == 0 then – return 1

• else – value = Ymod2 – return X**value * Power( X, Y/2 ) * Power( X, Y/2 )

• endif

Suggested Exercises Exercise 2.1.1, #3 0, if Y = 0 Mult( Y ) = 0 + Mult( Y/2 ) + Mult( Y/2 ) + 2, for Y > 0

Suggested Exercise Exercise 2.2.2, #1

Suggested Exercise Exercise 2.2.2, #3

Suggested Exercise Exercise 2.2.2, #4