ADVANCED ALGORITHMS REVIEW OF ANALYSIS TECHNIQUES (UNIT-1) 1 1. ALGORITHM : is a sequence of unambiguous instructions for solving a problem in a finite amount of time. Ex-1 : Write an algorithm to find the factorial of a given number n. Ex-2 : Write an algorithm for find the value of

m power n. 2 Ex-3 : Write an algorithm for finding the GCD of (m,n). Ex-4 : Find the GCD of 60, 24 using the method of common prime factors. Ex-5 : Find the minimum distance between any two elements in the array of size n. 3 ASYMPTOTIC NOTATION

1.1. What is the meaning of asymptotic. Consider a curve such as y = 1 / x As x increases, y decreases. The positive x-axis is an asymptote of the curve. As you continually increase x towards infinity, the value of y gets closer and closer to zero. Hence the curve gets closer and closer to the x-axis but never reaches it. We say the curve is asymptotic 4 1.2 Asymptotic Complexity : is a way of expressing the main component of the cost of an algorithm,

using idealized units of computational work. Ex-6 : Sorting the deck of cards. Cost Formula : 52 + 51 + 50 + + 2 So, CF = N(N+1) / 2 - 1 = (N2) + (N) 1 Here, the term N2 is dominating the CF. So, the behavior is said to be O(N2) . 5 1.3 Big-O Notation : f(n) - the cost function of an algorithm. g(n) - the cost function of another algorithm. Here, if f(n) <= g(n), then the algorithm with Cost Function f is faster than the other. Note : The Big-O is the formal method of

expressing the upper bound of an algorithms running time. 6 Definition : For non-negative functions f(n) and g(n), if there exists an integer n0, and a constant c > 0 such that for all integers n >= no 0 <= f(n) <= c g(n), then f(n) is Big-O of g(n). This is denoted as : f(n) = O(g(n)) Ex-7 : Let f(n) = 3n + 2, g(n) = n, c = 4 Show that g(n) is Upper Bound of f(n).

7 1.4 Big- Notation : For non-negative functions f(n) and g(n), if there exists an integer n0, and a constant c > 0 such that for all integers n > no f(n) >= c g(n), then f(n) is Big- of g(n). This is denoted as : f(n) = (g(n)) Ex-8 : Let f(n) = 3n + 2, g(n) = n, c = 3 Show that g(n) is Lower Bound of f(n). 8

1.5 Theta Notation : Def : For non-negative functions f(n) and g(n), if there exists an integer n0, and two constants c1,c2 > 0 such that for all integers n >= no c1 g(n) <= f(n) <= c2 g(n), then f(n) is Theta of g(n). This is denoted as : f(n) = (g(n)) Ex-9 : Let f(n) = 3n + 2, g(n) = n, andc1 = 3, c2 = 4 Find the probable value of n0. 9 Note : For non-negative functions, f(n) and g(n),

f(n) is theta of g(n), iff f(n) = O(g(n)) and f(n) = (g(n)) Ex-10 : Compare the two functions N2 and 2n /4 for various values of n. Determine when the second becomes larger that the first. Ex-11 : Determine the frequency counts for all statements in the following algorithms. s=0 for i = 1 to n do s = s + i; 10 Ex-12 : Determine the frequency counts for all statements in the following algorithms. x = 0;

n = 5; for i = 1 to n do for j = 1 to i do for k = 1 to j do x = x + 1; 1.6 Little-o Notation : Def : For non-negative functions f(n) and g(n), if there exists an integer n0, and a constant c > 0 such that for all integers n >= no 0 <=f(n) < c g(n), then f(n) is Little-o of g(n). This is denoted as : f(n) = o(g(n)) 11 Note : Let f(n) = 2n2 and g(n) = n2 and

c=2 Here, f(n) = O (g(n)) - Big-O But, f(n) o(g(n)) - little-o If f(n) = 2n & g(n) = n2, and c = 3, then f(n) = o(n2) Ex-13 : Let f(n) = 3n + 2 , g(n) = n2 and c = 6 Show that 3n+2 = o(n2) Note : For non-negative functions, f(n) and g(n), f(n) is little o of g(n), if and only if, f(n) = O (g(n)) and f(n) ( g(n) ) [ strict upper bound, no lower bound] 12 1.7 Little-Omega Notation : Def : For non-negative functions f(n) and g(n), if there exists an integer n0, and a constant c > 0 such that

for all integers n > no 0 <= c g(n) < f(n), then f(n) is Little- () of g(n). This is denoted as : f(n) = (g(n)) Note : Consider f(n), g(n) and h(n) are non-negative functions. here, f(n) = (g(n)) and g(n) = (h(n)) imply f(n) = (h(n)) 13 Ex-14 : Let f(n) = 3n + 2, g(n) = n and c = 3 Show that 3n+2 = (n) Note : For non-negative functions, f(n) and g(n), f(n) is little of g(n), if and only if f(n) = (g(n)) and f(n) ( g(n) ) [ strict lower bound, no upper bound] Ex-15 : Find the (n2) of (1/2) n2 - 3n.

Show that (1/2) n2 - 3n = (n2). Find C1 and C2. * * * * * 14 2. Standard Notations & Common Functions 2.1 Monotonicity : A function f(n) is monotonically increasing if m <= n implies f(m) <= f(n). A function f(n) is monotonically

decreasing if m <= n implies f(m) >= f(n). A function f(n) is strictly increasing if m < n implies f(m) < f(n). A function f(n) is strictly decreasing if m < n implies f(m) > f(n). 15 2.2 Floors & Ceilings: For any real number x, we denote the greatest integer less than or equal to x by x, (read as the floor of x) and the least integer greater than or equal to x by x, (read as the ceiling of x). For all real x, we have x1 < x x x < x+1

For any integer n, we have n/2 + n/2 = n .(2) .(1) Ex-16 : If x = 2.34 then Find the floor and Ceiling of x. 16 2.3 Modular Arithmetic: For any integer a and any positive integer n, the value a mod n is the remainder (or residue) of the quotient a/ n. Here, a mod n = a - na/n Ex-17 : Let a = 25 & n = 7,

Find the value of a mod n. 2.4 Exponentials : For all real a > 0, m, and n, we have a) a0 = 1 b) a1 = a c) a-1 = 1/a d) (am)n = amn e) (am)n = (an)m f) am an = am+n 17 2.5 Polynomials : Given a nonnegative integer d, a polynomial in n of degree d is a function p(n) of the form : d p(n) = a ai ni i=0 where the constants a0, a1, ., ad are the coefficients of the polynomial and ad 0.

2.6 Logarithms : The following are some of the notations : a) lg n = log2n b) ln n = logen c) lgkn = (lg n)k d) lg lg n = lg (lg n) 18 For all real a, b, c > 0, and n, we have e) a = blogb a f) logc(ab) = logca + logcb g) logban = n log ba h) logba = logca / logcb i) logb(1/a) = - logba j) logba = 1 / logab

k) alogbc = clogba A simple series expansion is : Ln(1+x) = x (x2/2) + (x3/3) - (x4/4) + (x5/5) - Here |x| < 1. 19 2.7 Factorials : The notation n! is defined for integers n 0 as n! = 1 if n = 0 = n. (n-1)! if n > 0 Thus, n! = 1.2.3n 2.8 Functional Iteration : We use the notation f(i)(n) to denote the function

f(n) iteratively applied i times to an initial value of n. Formally, let f(n) be a function over the reals. 20 For non-negative integers i, we recursively define f(i)(n) = n = f ( f(i-1)(n) ) if i = 0 if i > 0 Ex-18 : Let f(n) = 2n. g(n) = 2n+3 Then find the values of f(i)(n), g(i)(n) ? 2.9 The Iterated Logarithmic Function : The notation lg*n (read as log star of n) to denote The iterated logarithm, defined as :

Let lg(i)n be the logarithm function applied i times in succession, starting with argument n. 21 i.e., log(0)n = n log(1)n = log n log(2)n = log (log n) log(3)n = log (log (log n)) log(k+1)n = log (log(k)n) Thus we define the iterated logarithm function as : Log *n : = 0 , if n <= 1 : = 1 + Log * (log n), if n > 1. lg*2 = 1,

lg*16 = 3, lg*4 = 2 lg*65536 = 4 lg*(265536) = 5 22 The table for x, log star x is as follows : X : (-,1] Lg* x : 0 (1,2] (2,4] (4,16] (16,65536] (65536, 265536]

1 2 3 4 5 2.10 Fibonacci Numbers : Def : F0 = 0, F1 = 1, Fi = Fi-1 + Fi-2 for i 2 Thus, each fibonacci number is the sum of its previous two numbers. Ex : 0,1,1,2,3,5,8,13,21,34, Find the next five fibonacci numbers. 23

Golden Ratio : Fibonacci Numbers are related to the golden Ratio 1 and its conjugate 2, which are the two roots of the equation : x2 = x + 1 The values of 1 and 2 are : 1 = (1 + 5) /2 = 1.618 (Golden Ratio) 2 = (1 - 5) /2 = - 0.618 Let x = 2, y = (1 + 5) = (1 + 2.236) = 3.236 Draw a rectangle for (x,y), (x,y-x), 24 The relationship between FN and GR : In the above diagram, we can see that

y/x = x / (y-x) ..(1) In Fibonacci Sequence : For large values of n, we have Fn / Fn-1 = Fn-1 / Fn-2 ..(2) 25 But, Fn = Fn-1 + Fn-2 Fn-2 = Fn Fn-1 So, Fn / Fn-1 = Fn-1 / Fn-2 Fn / Fn-1 = Fn-1 / (Fn - Fn-1) If we replace, Fn with y and Fn-1 with x, we have y / x = x / (y x)

which is Golden Ratio. Compute any number in Fibonacci Sequence : Fn = n / 5 where F0 = 0, F1 = 1, F2 = 1, F3 = 2,.. * * * * * 26 3. Recurrences & Solutions of Recurrence Equations : 3.1 Divide-and-Conquer :

Divide : the problem into a number of subproblems that are smaller instances of the same problem. Conquer : the subproblems by solving them recursively Combine : the solutions to the subproblems into the solution for the original problem. 27 3.2 Recurrences : A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs. Ex-19 : The recurrence equation for Fibonacci is : F0 = 0, F1 = 1 Fi = Fi-1 + Fi-2 for i 2 Ex-20 :

Find the value of the recurrence equation g(0) = 0 g(n) = g(n-1) + 2n 1 using iteration. 28 3.3 Recurrence Equation : A homogeneous recurrence equation is written as : a0tn + a1tn-1 + . . . . + aktn-k = 0. Ex-21 : tn 3tn-1 4tn-2 = 0, for n >= 2. {Initial condition: t0=0, t1=1} Characteristic equation: xn 3x(n-1) 4x(n-2) = 0, or, x(n-2) [x2 3x 4] = 0,

or, x2 3x 4 = 0, or, x2 + x 4x 4 = 0, or, x(x+1) 4(x+1) = 0, or, (x+1)(x-4) = 0, Therefore, roots are, x = -1, 4. 29 So, the general solution of the given recurrence equation is: tn = c1*(-1)n + c2*(4n) Use t0 = c1 + c2 = 0, and t1 = -c1 + 4c2 = 1. Solve for c1 and c2, c1 = -(1/5), c2 = (1/5). So, the particular solution is: tn = (1/5)[4n (-1)n] = (4n) NOTE : The general solution for the original

recurrence equation is: tn = i=1kcirin 30 Inhomogeneous recurrence equation a0tn + a1tn-1 + . . . . + aktn-k = bnp(n), where b is a constant and p(n) is a polynomial of order n. Note : Homogenize the given equation to an equivalent homogeneous recurrence equation form. Ex-22 : Solve tn 2tn-1 = 3n. The concerned Homogeneous Equation is : tn+1 5tn + 6tn-1 = 0 Characteristic equation:

0. x2 5 x + 6 = General solution of the given RE is: 31 Ex-23 : Solve tn 2tn-1 = n. .(1) Replace n with n+1 tn+1 2tn = n+1 .(2) Subtract (1) from (2) : tn+1 3tn + 2tn-1 = 1 Replace n with n+1 tn+2 3tn+1 + 2tn = 1

.(3) ..(4) Subtract (3) from (4). tn+2 4tn+1 + 5tn - 2tn-1 = 0 ..(5) Now it is a homogeneous recurrence equation 32 3.4 Analysis of Insertion Sort : Input: A sequence of n numbers _a1, a2, . . . , an_. Output: A permutation (reordering) a1, a2, . . . , an of the input sequence such that a1< a2 < . . . < an Ex-23:

524613 254613245613 245613 124563 123456 INSERTION-SORT(A) 1) for j 2 to n 2) do key A[ j ] 4) i j - 1 5) While i> 0 and A[i] > key 6) do A[i+1] A[i] 3)/* Insert A[ j ] into the sorted 7) ii-1 sequence A[1 . . j 1]. */ 8) A[i+1] key 33

Statement No 1 2 3 4 C1 C2 0 C4 Cost Times n n-1 n1

n-1 5 C5 tj j=2 to n 6 C6 (tj-1) j = 2 to n 7 C7 (tj-1)

j = 2 to n 8 C8 n-1 34 The running time of the algorithm is (cost of statement) (no. of times statement is for all statements executed) Let T (n) = running time of INSERTION-SORT. T (n) = c1 n + c2 (n 1) + c4 (n 1) +

C5 tj + C6 (tj - 1 ) + C7 (tj - 1 ) + j=2 to n j=2 to n j=2 to n c8 (n 1). 35 Best case: The array is already sorted. Always find that A[i ] key upon the first time the while loop test is run (when i = j 1). All t j are 1. Running time is T (n) = c1n + c2(n 1) + c4(n 1) + c5(n 1) + c8(n 1)

= (c1 + c2 + c4 + c5 + c8)n (c2 + c4 + c5 + c8) Can express T (n) as an +b for constants a and b (that depend on the statement costs ci ) T (n) is a linear function of n. 36 Worst case: The array is in reverse sorted order. Always find that A[i ] > key in while loop test. Have to compare key with all elements to the left of the j th position compare with j 1 elements. Since the while loop exits because i reaches 0, there the j 1 tests tj = j . tj = j j=2 to n j=2 to n and (tj -1) j=2 to n

= (j - 1) j=2 to n Here j = [n(n+1)/2] - 1 j=2 to n 37 Letting k = j 1, we see that (j 1) = k = n(n-1)/2 j=2 to n k=1 to n-1 So, Running Time is : T (n) = c1n + c2(n 1) + c4(n 1) + C5 [n(n+1)/2 - 1] + C6 [n(n-1)/2] + C7 [n(n-1)/2] + c8 (n 1) = [c5/2 + c6/2 + c7/2] n2 + [c1 + c2 + c4 + C5/2 c6/2 c7/2 + c8] n [c2+c4+ c5+c8] Can express T (n) as an2 + bn + c for constants a, b, c (that

again depend on statement costs) T (n) is a quadratic function of n. 38 3.5 Recurrence Relations : A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely : a0, a1, a2, , an-1, for all integers n with n n0, where no is a nonnegative integer. Ex-24 : Is an = 3n, the solution of the recurrence relation, where an = 2. an-1 an-2. for n = 2,3,4 Ex-25 : Is an = 5, the solution of the recurrence relation, where an = 2. an-1 an-2. for n = 2,3,4 39

Ex-26 : Some one deposits Rs. 10,000 in a savings account at a bank yielding 5% per year with interest compounded annually. How much money will be in the account after years. 30 Ex-27 : Let an denote the number of bit strings of length n that do not have two consecutive 0s (valid strings). Find a recurrence relation and give initial conditions for the sequence {an}. 40 Ex-28 : What is the solution of the recurrence relation for the following.

an = an-1 + 2an-2 with a0 = 2 and a1 = 7. Find its Characteristic Equation. Ex-29 : Prove that the following is explicit formula for Fibonacci Numbers. fn= (1/5)[(1+5)/2]n - (1/5)[(1-5)/2]n Find its Characteristic Equation. 41 Ex-30 : Find the solution of recurrence relation an = 6an-1 - 9an-2 with a0 = 1 and a1 = 6. The Characteristic Equation is : r2 -6r+9=0 The only root is 3. Hence the solution to the RR is : an = c1 3n + c2 n 3n The Value of C1 = 1 and C2 = 1 Solution : an = 3n + n 3n

42 3.6 Solving Recurrences : Ex-31 : Find number of calls for a plain recursive Fibonacci To compute the Fibonacci numbers fn, f0 = 0, f1 = 1, and fn = fn1 + fn2, for n > 1. Denote by cn = #calls to compute fn. c2 = 2, c3 = 4 = 22, c4 = 8 = 23 Following the recursion: cn = cn1 + cn2 + 2 = . So, the value of cn is O(2n). 43 a) The Substitution Method The substitution method for solving recurrences consists of two steps:

1 Guess the form of the solution. 2 Use mathematical induction to find constants in the form and show that the solution works. We substitute the guessed solution for the function when applying the inductive hypothesis to smaller values. Hence, the name substitution method. We can use the substitution method to establish either upper or lower bounds on a recurrence. 44 Ex-32 : Solve T(n) = 2T(n/2) + n Solution : Guess T(n) cn log n for some constant c (that is, T(n) = O(n log n)) Base case: we need to show that our guess holds for some base case (not necessarily n = 1, some small n is ok). Ok, since function constant for small constant n. Assume holds for n/2:

T(n/2) c. (n/2) log(n/2) Prove that holds for n: T(n) cn log n , if c >=1. 45 Ex-33 : Solve T(n) = 2 1 <= n < 3 = 3. T( n/3 ) + n n >= 3 Prove that T(n) = O(n log n) for all n >= m. Here we have to show that T(n) <= c n log n Observe T(n) = 3 T ( n/3 ) + n <= 3. c n/3 log n/3 + n

<= 3. c (n/3) (log n 1) + n = c n log n c n + n But, T(n) <= c n log n, if (- cn + n) <= 0 implies c >= 1 Let m = 3 implies n = 3. 46 Here T(3) < = 3 c implies c >= T(3) / 3 But, T(3) = 9 implies C >= 3 Case-1 : Since T(3) = 3 . T( n/3) + 3 = 9 cn log n = 3.3 log 3 = 9 proved. Case -2 : Let n > 3. T(n) = 3. T( n/3) + n <= 3.3. n/3. log n/3 + n <= 9. n/3. ( log n 1) + n = 3 n (log n 1 ) + n = 3 n log n 3 n + n = 3 n log n 2 n

<= 3 n log n proved 47 b) The Recurrence-Tree Method A recursion tree is useful for visualizing what happens when a recurrence is iterated. It diagrams the tree of recursive calls and the amount of work done at each call. solving recurrences : expanding the recurrence into a tree summing the cost at each level applying the substitution method. Ex-34 : Solve T(n) = 2T(n/2) + n2. 48

The recursion tree for this recurrence has the following form, which has the solution O(n2). T(n) = 2T(n/2) + n2. n2 n2 (n/2)2 (n/2)2 n2/2 (n/4)2 (n/4)2

n2 /4 (n/8)2 (n/8)2 . n2 /8 49 Ex-35 : Draw the Recurrence Tree for the following. T(n) = 3T(n/4) + cn2. cn2 c(n/4)2

c(n/16)2 cn2 c(n/4)2 c(n/16)2 c(n/4)2 c(n/16)2 (3/16)cn2 (3/16) 2cn2 The last term here is : (3/16) i cn2 The above recurrence Tree has the order of O(n2)

50 Ex-36 : Draw the Recurrence Tree for the following. T(n) = 8T(n/2) + n2. [T(1)=1] T(n) = n2 + 8 T(n/2) = n2 + 8 [ (n/2)2 + 8. T(n/22) ] = n2 + 8 (n2/4) + 82 T(n/22) = n2 + 2 n2 + 82 T(n/22) = . = n2 + 2 n2 + 22 n2 + 83 T(n/23) = = n2 + 2 n2 + 22 n2 + 23 n2 + .. + 8i T(1) Here, n/2i = 1 implies i = log n Therefore, last term = 8log n 51 Here, T(n) =

n2 + 2 n2 + 22 n2 + 23 n2 + .. + 2log n-1 n2 + 8log n = 2k n2 + 8log n k = 0 to log n 1 = n2 2k + (23)log n k = 0 to log n 1 Here, The first term is of the order (n).n).). (23)log n = (2log n)3 = n3

Therefore T(n) = n2 (n).n).) 52