Problem 1. Assume you have an array A1.., n], where every value is an integer be

Question

Problem 1. Assume you have an array A1.., n], where every value is an integer between 1 and n, inclusive. You do not have direct access to the array A. You do have a function equal(i,j) that will return TRUE if Ai ALj], and FALSE otherwise. (a) Give a quadratic (en*) algorithm that counts the number of pairs (A[i],AJ) (i j) such that AM-Aj]. The algorithm can only use a constant amount of extra memory. Just give the "brute force" algorithm. (b) Analyze exactly how many times the algorithm calls equal(i,j) (as a function of n) Justify.

Explanation / Answer

(a): first we will write the heta(n^2) solution using C like pseudo code,

int count = 0;

for( int i = 1; i<=n;i++){

   for(int j =1 ;j<=n,j++){

      if(i !=j){

         if(equal(i,j)){

            count = count + 1;

         }

      }

   }

}

Here the count will have the number of elements have equal values.

b) clearly it calls equal(i,j) every time the loops execute except when i == j,

so the total number of time equal(i,j) is called is n^2 - n or n*(n-1) times.

P.S: if you like the answer give us a thumbs up.

Happy chegging!

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.