Question

The following algorithm returns true if the n items in an array are all distinct, i.e., if no two items are equal to each other, otherwise it returns false. 1 ALGORITHM UniqueElements(A[1..n]) 2 // Determine whether all the elements in an array are distinct 3 // Input: Array A[1..n] 4 // Output: “true” if all elements of A are distinct, “false” otherwise 5 for i ← 1 to n – 1 do 6 for j ← i + 1 to n do 7 if A[i] = A[j] return false 8 return true The basic operation is the comparison of two array elements at line 7. Determine the number of basic operations performed for an input of size n. Write your answer in simplest form, if possible.

Answer 1

So, as you said I will try to be as simple as I can.

So, algorithm for the given problem is :

for i ← 1 to n – 1 do 
      for j ← i + 1 to n do 
             if A[i] = A[j] 
                   return false 
return true

Now, let's talk about the number of operations performed in terms of n.

for i ← 1 to n – 1 do             //------------> O(n){as loop is running from 1 to n) that means n times loop is running and checking the condition also that the loop condition holds good and loop will continues to run. Hence number of operations are n.
      for j ← i + 1 to n do       //------------> O(n*n)(as loop is running from i+1 to n) that means in worst case it will run n times which will be similarly takes O(n) time and this same O(n) time will be repeating n times . Hence total operations will be O(n*n) 
             if A[i] = A[j]       //------------> O(n*n)(as it is written in the nested loop which is performing O(n*n) operations, so this will also runs O(n*n) times)
                   return false  //-------------> O(1) it will executed only 1 time
return true                       //-------------> O(1) it will executed only 1 time



Hence, total operations of this algorithm will be:

                              O(n) + O(n*n) + O(n*n) + O(1) + O(1)

Hence, as we know O will be written as the maximum operation in the expression:


So, O(n*n) will be the total operations performed in the algorithm

So, this was the solutions of the problem.
I hope I am able to solve your problem, if yes then do give it a like.
It really helps :)