Scribd
Upload
16 views1 page

Duplicate Detection Algorithm in Arrays

The document describes an algorithm for checking duplicates in an array, using nested loops to compare each element with the subsequent elements. It returns TRUE if duplicates are found and FALSE otherwise. The time complexity of the algorithm is O(n^2), as illustrated by an example with an array of ten unique elements.

Uploaded by

ruthwangari133
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
16 views1 page

Duplicate Detection Algorithm in Arrays

The document describes an algorithm for checking duplicates in an array, using nested loops to compare each element with the subsequent elements. It returns TRUE if duplicates are found and FALSE otherwise. The time complexity of the algorithm is O(n^2), as illustrated by an example with an array of ten unique elements.

Uploaded by

ruthwangari133
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

(a) Let take Array to be the name of the array and n be its size

Array[n] /* Array declaration */


Int i, j, n /* Variables declaration */
for (i = 0, i< n - 1, i++) /* Checking if ith index value has a
duplicate */
for (j = i + 1, j < n, j++) /* Range of next value (i+1) to n */
if (Array[i]==Array[j]) /* Making comparison to check if the
values are the same */
return TRUE /* return if duplicates are found*/
return FALSE /* return if duplicates are not found */

(b)

(c) Time complexity

Let’s use the example below:

If Array[10]={10, 20, 30, 40, 50, 60, 70, 80, 90, 100}, then the algorithm will not find any
duplicates.

for (j = i + 1, j < n, j++) iterates as below:

(n)*(n – 1)/2 = n2 – n/2

The worst case is therefore O(n2)

You might also like