Question

Consider the following recursive method for finding the maximum element in an int array:

public int static max(int[] a, int lo, int hi) {
  if (lo > hi) return a[lo];
  int mid = (lo + hi) / 2;
  int loMax = max(a, lo, mid);
  int hiMax = max(a, mid+1, hi);
  if (loMax > hiMax)
    return loMax;
  else
    return hiMax;
}

Write down the recurrence relation for counting the number of times the comparison if (loMax > hiMax) is performed. Use the recurrence relation for merge sort as a model.

Answer 1

Recurrence Relation: - Here we are dividing entire list of n elements into 2 Half and again each Half, we are applying procedure Recursively. Assume All initialization, comparison will take constant time i.e 0(1) T(n) = 1 + T(n/2) + T(n/2) T(n) = 2T(n/2) + 1 rightdoublearrow 0(n) therefore maximum of n comparisons will possible to find Max element in an arras T(n) = 2 T(n/2) + 1 = 2[2T(n/4) + 1] + 1 = 2^2 T(n/4) + 2 + 1 = 2^2[27(n/8) + 1] + 2 + 1 = 2^3 T(n/8) + 2^2 + 2 + 1 = 2^k middot T(n/2^k) + 1 + 2 + 2^2 + ..... + 2^k-1 Let n/2^k = 1 rightdoublearrow n = 2^k s_n = a(r^n - 1/r- 1) = n T(1) + 1(2^K - 1)/1 = n(1) + n - 1 = 2n - 1 0(n) Note: n = 1 rightdoublearrow no comparison