Question

The following divide-and-conquer algorithm is designed to return TRUE if and only if all elements of the array have equal values. For simplicity, suppose the array size is n=2k for some integer k. Input S is the starting index, and n is the number of elements starting at S. The initial call is SAME(A, 0, n).

Boolean SAME (int A[ ], int S, int n) { Boolean T1, T2, T3; if (n == 1) return TRUE; T1 = SAME (A, S, n/2); T2 = SAME (A, S + n/2, n/2); T3 = (A[S] == A[S + n/2]); return (T1 ∧ T2 ∧ T3); }

1. Explain how this program works.

2. Prove by induction that the algorithm returns TRUE if and only if all elements of the array have equal values.

3. Let f(n) be the number of key comparisons in this algorithm for an array of size n. Write a recurrence for f(n).

4. Find the solution by repeated substitution

Answer 1

As we know that Divide and Conquer Algorithm works in three parts .....

1. Divide: This involves dividing the problem into some sub problem.
2. Conquer: Sub problem by calling recursively until sub problem solved.
3. Combine: The Sub problem Solved so that we will get find problem solution

/**************************************************************************************************************************/

O(1) if n is small

T(n) = f1(n) + 2T(n/2)  

----> 2T(n/2) is for we call TWO TIMES the function SAME .

Time complexity for SAME => T(N/2)

----> f1(n) for comparison

Thus O(f(n)) ==> NLOG(N) .......

Boolean SAME (int A[ ], int S, int n) ->setp 0
{
Boolean T1, T2, T3;
if (n == 1) return TRUE; -> step 1
T1 = SAME (A, S, n/2); -> step 2 -> T(n/2)
T2 = SAME (A, S + n/2, n/2); ->setp 3 -> T(n/2)
T3 = (A[S] == A[S + n/2]); -> step 4
return (T1 ∧ T2 ∧ T3); -> step 5
}

Let we take an example :-

-> Array is A[2,2,2,2,2]
-> Starting index S = 0
-> Length of Array n = 5

->step 0 --- Call to SAME(A,0,5)

->step 1 --- as n == 5 then condition is FALSE

->step 2 --- T1 = SAME(A,0,2) == true (return from step 2(5))
  
-> step 2(0) --- T1 = SAME(A,0,2)
  
->step 2(1) --- as n == 2 then condition is FALSE
  
->step 2(2) ---

-> step 2(2)(0) --- SAME(A,0,1)

  
-> step 2(2)(1) --- as n==1 then return TRUE

Then we return from step 2(2)(1) to step 2(0) AS TRUE
  
->STEP 2(3) --- T2 = SAME(A,0+1,1) ---> return to step 3 as TRUE

-> step 2(3)(0) --- SAME(A,1,1)

-> step 2(3)(1) --- as n == 1 then return TRUE

Then we return from step 2(3)(1) to step 2(3)

-> step 2(4) --- T3 = (A[0] == A[0+1]) => T3 = TRUE
  
-> step 2(5) --- T1^T2^T3 = 1 ^ 1 ^ 1 = 1
  
Thus return step 2 as TRUE

-> step 3 --- T3 = SAME(A,1,2) == true (return from step 3(5))

-> step 3(0) --- SAME(A,1,2)

-> step 3(1) --- T1 = SAME(A,1,1)
  
->step 3(1)(0) --- SAME(A,1,1)

->setp 3(1)(1) --- as n == 1 then return TRUE

-> step 3(2) --- T2 = SAME(A,2,1)
  
-> step 3(2)(0) --- SAME(A,2,1)
  
-> step 3(2)(1) --- as n == 1 then return TRUE
  
-> step 3(4) --- T3 = (A[1] == A[1+1]) => T3 = TRUE
  
-> step 3(5) --- T1^T2^T3 = 1 ^ 1 ^ 1 = 1
  
Thus return to step 3 as TRUE
  

-> step 4 --- T3 = (A[0] == A[0+2]) => T3 = TRUE

-> step 5 --- T1^T2^T3 = 1 ^ 1 ^ 1 = 1

Thus return to TRUE as RESULT