2 Let fn denote the number of comparisons between pairs of e

2. Let f(n) denote the number of comparisons (between pairs of elements of a list) that are required to perform the above algorithm on a list of length n. State the recurrence relation that holds for f(n) where n is even.

3. Give a big-O estimate for f(n).

Input: A list a1, an. Output: The minimum element of the list begin if n 1 then return al else Ln/2 L2 am+1, an (L1) Min MinAlgo (L2) then L return ti else L return

Solution

1) t1<t2

i.e. returning min element from t1 and t2.

2) Number of comparisions given is f(n). The sub array length is n/2. and there are 1 comparisions in the base case. So the recurence relation is T(n)=T(n/2)+f(n).

3) =>T(k)=T(k/2) k>=2 and T(1)=1;

=> recurrence tree metho we get O(log₂n)