% Recursive definition of n factorial function fact(n) { if (n == 0) then return(1) else return(n*fact(n)) } Equations: T(n) = C + T(n-1) T(0) = D Solution: T(n) = Cn + D. ************************************************************ % Binary search for X through sorted array A between indices LOW and HIGH. % Check the middle element A[MID]. If A[MID] > X, then search the first half % of the array; otherwise search the second half. function boolean bsearch(X, A, LOW, HIGH) { if (LOW == HIGH) return(A[LOW]=X); MID = (LOW + HIGH) /2; if (A[MID] == X) return(true); if (A[MID] > X) return(bsearch(X,A,LOW,MID-1)); return(bsearch(X,A,MID+1,HIGH)); } Equations: Let n = HIGH + 1 - LOW (the number of elements being searched) T(n) = C + T(n/2) T(1) = D Solution: T(n) = D + C lg(n) ************************************************************ % Recursive routine for finding the largest element in array A between % LOW and HIGH. Recursively find the largest elements in the first half and % in the second half and take the larger of those. NOTE: This is a pointless % way to do this, used only for illustration. } function biggest(A,LOW,HIGH) { if (LOW == HIGH) return(A[LOW]); MID = (LOW + HIGH) /2; return(max(biggest(A,LOW,MID), biggest(A,MID+1,HIGH))); } function max(X,Y) { if (X > Y) return(X) else return(Y) } max has Theta(1) running time. Equations for biggest: Let n = HIGH + 1 - LOW T(n) = 2*T(n/2) + C T(1) = D Solution: T(n) = Dn + C(n-1) ************************************************************ % Binary search through sorted linked list. Look for element X among the first % N items of list L. Analogous to bsearch above. NOTE: This is a useless % routine, used only for illustration function lsearch(X,L,N) { if (N == 0) return(false); if (N == 1) return(L.value == X); HALF = N/2; HALFWAY = nth(L,HALF); if (HALFWAY.value == X) return(true); if (HALFWAY.value > X) return(lsearch(X,L,HALF)); return(lsearch(X,HALFWAY.next,N-HALF-1)) } % nth(L,K) returns the Kth tail of linked list L } function nth(L,K) { for (i = 0; i