SIT L03 Recursion - Recurrence Relations, Fibonacci Sequence, Algorithms PDF

SIT Internal L03: Recursion  SIT Internal Recurrence relations: Fibonacci sequence Fibonacci. ! , T, 2, 3, 5, 8. fsequence: 2 = f1 1 + 13.21.34... 0 +' fo = 1...

SIT Internal L03: Recursion  SIT Internal Recurrence relations: Fibonacci sequence Fibonacci. ! , T, 2, 3, 5, 8. fsequence: 2 = f1 1 + 13.21.34... 0 +' fo = 1 Recurrence relation: an f3 = + :t2 f3 f 2 —* 1 -F -*- 1* equation that relates the -*- f4 =3 + fi = 3 -F 22 nt ** element f of a f3 f4 = = 5 sequence to some predecessors.off its —-i f5 to. ii We need an i n i t i a l fn ' (fn—1+ fn—z) for n 2: 2 c o n d it io n that provides the starting f1 y initial values for a finite number of elements of the Condition sequence.  SIT Recursive Internal RE 0F TE CH NO caiis LO GY Used frequently in computer programs. A recursive function calls itself. Example The factorial function: n! = 1 x 2 x 3 --- (n — for n D: 1) x n 1. 0! = 1 by definition. Hence, n! = n x (n — 1)! for n Zt 1. factorial(n) —— n x factorial(n — 1)  SIT Internal Exampie: ! A test for if n==O: the BASE CASE answer (initial condition) answer enables the return recursive answer calls to A shorter version stop. that does exactly the Each recursive same thing: call solves an identical (but smaller) problem. return n’factoiial(n—1)  SIT Anatomy of a Internal recursive caii return factorial(n) 120 : factorial(5 ż£ n==0 : ) answer = an s wc x 5*factoc:J return factorial(4) 24 answer = 4*factorJ answer n’factoiial(n—1) l(3 return factorial(3) 6 return answer answer = 3*factori return Remember that each 2 call to a function factori (2) answer = return starts that function 2*factorial factorfal(1) 1 anew. That means it answer = 1*factori l(0 return has its own copy of BASE factoria 1 (0) any local values, CASE answer = 1 including the values of the parameters.  SIT Example: Time Analysis Internal for N! factorial(n) —— n z factorial(n — I) Let T(n) be the number of multiplications needed to compute factorial(n). T[n) = T(n — 1) -t 1 T(0) = 1 T(n — 1) multiplications are needed to compute factorial(n — 1), and one more multiplication is needed to multiply the result by n.  SIT Internal Exampie: Time Analysis for factorial N! Using the method of backward subst i f u t i o n s T(n) =—— [T(n T[— n 2) — + it1) -t =1[ T(n-1-1)+1 + i ]+1 —— T(n — 2) -t 2 = [T(n — 3) + 1] + 2 = [T(n — n) +1] + (n — —— T(n — 3) 1) T -t 3 ^) ” Time efficiency of ' ’r(0 ) ^ ” the recursive n! ^ algorithm iS of = 1 -t O(n).  SIT Internal Beauty of Recursive Algorithms /(0) = 1 f(n) = n x foctorio/(n — 1), n T 1 Direct translation between the recurrence relation and the recursive algorithm factorial(n): return n’factoiial(n—1)  SIT Internal SINGAPO Strategy for Designing Recursive RE INSTITUTE 0F Algorithm TECHNOLO GY 1. Identify the recurrence relation to solve the problem. 2. Translate the recurrence relation to a recursive algorithm. 3. Take note to translate the initial condition in the recurrence relation into the BASE CASE for the recursive algorithm.  SIT Internal Recursive vs. Iterative One should be careful with recursive algorithms because their conciseness, clarity and simplicity may hide their inefficiencies.  SIT Example: Fibonacci Internal Sequence Recall that: /n = (/n—i +fn—z) !!!! 0, (initio/ condition) /i' /o' f(n) żf : re t u rn 0 n==0: r e t u r n 1 if n>= 2: return f(n-1) + f(n- 1f 2) n==1:  SIT Example: Fibonacci Internal Sequence An iterative algorithm for the Fibonacci numbers has running time of 0 (n ). But using recursion, each call leads to another two calls: f(n — 1) and f(n — 2).  SIT Example: Fibonacci Internal Sequence qdef f ( n ) : 1f return 0 n==0 : return 1 1f return f(n - + f(n - n==1 : 1) 2) 1f n›= 2 :  SIT Example: Fibonacci Internal Sequence qdef f ( n ) : 1f return 0 n==0 : return 1 1f return f(n - + f(n - n==1 : 1) 2) 1f n›= 2 :  SIT Example: Fibonacci Internal Sequence qdef f ( n ) : 1f return 0 n==0 : return 1 1f return f(n - + f(n - n==1 : 1) 2) 1f n›= 2 :  SIT Example: Fibonacci Internal Sequence qdef f ( n ) : 1f return 0 n==0 : return 1 1f return f(n - + f(n - n==1 : 1) 2) 1f n›= 2 :  SIT Example: Fibonacci Internal Sequence qdef f ( n ) : 1f return 0 n==0 : return 1 1f return f(n - + f(n - n==1 : 1) 2) 1f n›= 2 :  SIT Example: Fibonacci Internal Sequence qdef f ( n ) : 1f return 0 n==0 : return 1 1f return f(n - + f(n - n==1 : 1) 2) 1f n›= 2 :  SIT Example: Fibonacci Internal Sequence qdef f ( n ) : 1f return 0 n==0 : return 1 1f return f(n - + f(n - n==1 : 1) 2) 1f n›= 2 :  SIT Example: Fibonacci Internal Sequence qdef f ( n ) : 1f return 0 n==0 : return 1 1f return f(n - + f(n - n==1 : 1) 2) 1f n›= 2 :  SIT Example: Fibonacci Internal Sequence qdef f ( n ) : 1f return 0 n==0 : return 1 1f return f(n - + f(n - n==1 : 1) 2) 1f n›= 2 :  SIT Example: Fibonacci Internal Sequence qdef f ( n ) : 1f return 0 n==0 : return 1 1f return f(n - + f(n - n==1 : 1) 2) 1f n›= 2 :  SIT Example: Fibonacci Internal Sequence The total number of calls grows exponentially. qde f ( n ) : f 1f return 0 n==0 : return 1 1 f n==1 return f(n - + f(n - : 1) 2) 1 f n›= 2:  SIT Internal Example: Fibonacci Sequence Running time of recursive Fibonacci algorithm g f(n ) : żf : refurn 0 if n==1: return 1 ó if n>= return f(n-1) + f(n-2) 2: T(n) ——Tn( — 1) -i- T(n — 2) T(0) = ł, T(1) = 1 It can be shown that T(n) = Iż  SIT Internal SINGAPOR Compute Fibonacci: Recursive vs. Non- E INSTITUTE 0F recursive TECHNOLO GY Big-0 ComplexiÇ 90 0 600 O(n^ 2) 0 1 2 3 4 50 60 70 80 90 IO 0 0 0 0 Cement O s  SIT Internal Example: Binary Search Goal. Given a sorted array and a key. Find index (location) of the key in the array. Binary search. Compare key against middle entry. 1. Smaller, search in the left half. 2. Bigger, search in the right half. 3. Equal, return the index. 4. Size = = cn (Ig n) —+nn(c cn Ig(n/2) T(n/2)=c(n/2)19(n/2) — 1) Ig(n/2) = Ign — 192 6 cn (Ig n) for c z Ig2=1 This 1 completes the proof, in which, T(n) = cn (Ig n) —cn + n 6 0(n Ig n). cn (Ig n)  SIT Substitution Internal Example - Case 2: Using substitution method, find the solution to T(n) recurrence T(n/2) + n Ig n =2 Guess #1: Let us guess that the solution is T(n) = O(n T(n)Ig=n) 2 thus, [ T(n/2) ] + n Ig n t ) 2[c n/ n/2 :g n/2 lg(n/2) ] 2 n/2 + n Ig n cn (Ig n) — cn = cn Ig(n/2) + n Ig n + n Ig n ' :s C A kg n - cn + n Ig n (cn+n) Ig n — = (c+1)n Ig cn = (c+1) n Ig n - n — cn The Since we cannot make this lastcn equation to be guess less is wrong: than cn Ig n. can never be 6 [ (c+1)n Ig n — cn ] not :s ccnn (Ig Ig n) n  SIT Substitution Internal Example - Case 2: (cont.) Using substitution method, find the solution to recurrence T(n) = 2 T( [n/2] ) + n Ig n. Guess #2: Let us guess that the solution is T(n) = O(n2). Thus, T(n) 2 [ T(n/2) ] + n Ig n 6 2 [ (c. (n/2)2 ) ] + n Ig n ?’›(cn2) + n Ig n c n 2 12(cn2) + n Ig n The lastsequation is true for c 1 2, and thus, 2 2 T(n) =c nO(n ).  SIT Substitution Internal Remarks on Guessing in Substitution Method Remark: There is no general way to guess the correct solutions to recurrences. However, if a recurrence is similar to one you have seen before, then guessing a similar solution is reasonable. For example, T(n) = 2 T(n/2 + 17) + n which is a similar to T(n) = 2 T(n/2) + n asymptotically is bounded on 0(n Ig n). Another way to make a good guess is to loose upper and lower bounds on the recurrence and then reduce the range of uncertainty.  SIT The Recursion-tree Internal Method A difficulty in using the substitution method is how to come up with a good guess. The recurrence tree solves this problem by showing the cost of each sub-problem. Recursion trees are particularly useful when the recurrence describes the running time of a divide- and-conquer algorithm.  SIT Internal SINGAPORE The Recursion-tree INSTITUTE T 0ECHNOLOGY Method Example: Find a solution to recurrence T(n) = 2 T(b/2) + n. Create a recursion tree for the recurrence T(n) = 2 T(n/2) + n Time/Cost Ig n The running time of this recurrence is (n Ig n).  SIT The Master Internal Method The master method (if it can be applied) can determine easily a solution to recurrences of the form T(n) = a. T(n/b) + f(n) where a z 1 and b > 1 are constant and f(n) is an asymptotically positive function. In this recurrence, a sub-problems are solved recursively, —The problem is divided into ‘a’ sub-problems, each handles n/b number of data and requires time T(n/b), and —f(n) = D(n) + C(n) is the cost of dividing the problem and combining the results of the sub-problems.  SIT B3. The Master Internal Method (The Master logo a) " n ' ^^°)+°-- n° n ' n ‘) ^^°) ‘ theorem) Let a z 1 and b > 1 be constants. The recurrence T(n) = a T(n/b) + f(n) can be bounded Case If asymptotically as follows Then (3 1cases): f(n) = 0(n(* b°)"‘), for some constant c > T(n) = B(n' ^b °) 0 2 f(n) = 6(n*”^b°) T(n) = 6(n*”^b° Ig n) f(n) = ¢/(n(* b°)”‘), 3 for some constant c > 0, and if a T(n) = 6( f(n) ) f(n/b) 6 c f(n) for some constant c < Det. f(n) or n* ^ b ° is the larger one 1 and all sufficiently large n if n* b ° is larger case 1, if f(n) is larger case 3, if both equal then case 2  SIT B3. The Master Internal Method Remarks: To apply the master method some conditions must be satisfied. (Case 1) not only must f(n) < n'”^^°, it must be polynomially smaller. That is, f(n) must be asymptotically smaller than n*” ^° by a factor of n" f(n) < if c=0, then n 0=1, case 2; if for somen constant c > 0. /t c n'”* b " but not polynomially larger. If the function f(n) falls into one of these gaps, or if the regularity condition in case 3 fails to hold, the master method cannot be used to solve the recurrence.  SIT Internal SINEaPO RE INSTITUTE 0F TECHNOL OGY f(n)=1 and g(n)=n2. Then f(n) is polynomially smaller than yy g(n) 2 f(n)= 1+, o n and g(n)=n Then f(n) is polynomially f(n)=log n and g(n)=n. Then f(n) is not smaller than g(n) polynomially larger smallerthan nor g(n) T(n) = 4 7 ( ) -F 1a=4, b=2, n' O ^ 4 =n 2 is polynomial larger than the constant function 1. Thisn°is case 1 of the T(n) = + log n a=4, b=2, is not polynomially master's theorem. smaller2 log 4T ( ) nor polynomially larger than n. None of the three n cases of master's theorem can be applied.  SIT Internal SINGAPO INSTITUTE RE TECHNOL 0F OGY Chart 1000 Title 90. 0 80. 0 Chart 70. 60. 0 Title 0 50. 0 40. 2. 0 30. 0 0 20. 0 0. 100 0 1 2 3 4 £ 6 7 8 9 10 11 12 13 14 IN 16 17 18 n^0. n/ 0. 5 Ign 0 1 2 3 4 £ 6 7 8 9 10 11 12 13 IN 16 17 18 19 14 20 nlg n  SIT B3. The Master Internal Method Example T(n) = a. T(n/b) + 1: Solve the recurrence T(n) = 9 T(n/3) f(n)+ n For this recurrence, we have a=9, b=3, f(n)=n, and thus 2 n' ^" —- n' = n Since n 6 n!2-*)for 0 < c 6 1, (i.e. n n(2-1)) thus we apply case 1 which is f(n) = O(n(*”^^°)"’), where 0 < c 6 1 1 Thus, f(n) = the solution 0(n(*” to for ^°)"‘), thissome recurrence T(n) is T(n) = o ^ b °) = B(n' 6(n 2 ). constant c>0 2 f(n) = 6(n*O^b°) T(n) = 6(n* O ^ b ° Ig n) f(n) = ¢/(n(*” ^°)”‘), for some 3 constant c > 0, and if a f(n/b) 6 c T(n) = 6( f(n) ) f(n) for some constant c < 1 and all sufficiently large n  SIT B3. The Master Internal Method Example T(n) = a. T(n/b) + f(n) 2: Solve the recurrence T(n) = T(2n/3) + 1 For this recurrence, we have a=1, b=3/2, f(n)=1, and thus n'”**^" —- n*” / 2 1 — n 0 — 1 Since f(n) = B(n('”* b ")) = 6(1), case 2 applies 1 f(n) = 0(n(*” ^°)"‘), for some T(n) = Thus, the solution to this recurrence is T(n) = B(n' o ^ b °) constant c > 0 2 6(1xIg f(n) = n). 6(n*O^b°) T(n) = 6(n* O ^ b ° Ig n) f(n) = ¢/(n(*” ^°)”‘), for some 3 constant c > 0, and if a f(n/b) 6 c T(n) = 6( f(n) ) f(n) for some constant c < 1 and all sufficiently large n  SIT B3. The Master Internal Method T(n) = a. T(n/b) + Example f(n) 3: Solve the recurrence T(n) = 3 T(n/4) + n Ig n For this recurrence, we have a=3, b=4, f(n)=n Ig ^° n, and thus n' — n*”''*4 — Since3 — n Ig 0.793) 0 7 3 O(nn >n f(n) = f2 (n( 43)”‘), c - 0.2 (i.e. 0, and T(n) = 3 case if a 2 and case f(n/b) 3 (i.e. 6 c f(n) for The somemaster method constant cannot c < 1 and 6( f(n beallapplied). sufficiently large n ))