#include <stdio.h>
main()
{
int
a[10]={1,2,1,1,2,3,2,3,3,4},b[10],i,j=0,c,flag;
b[0]=a[0];
for(i=1;i<10;i++)
{
flag=0;
for(c=0;c<=j;c++)
{
if(a[i]==b[c])// check whether a[i] is present in entire b array
{
flag=1;
break;
}
}
if(flag
== 0)
{
b[++j]=a[i];
}
}
printf("the
array elements after removing duplicate values are\n");
for(i=0;i<=j;i++)
printf("%d\t",b[i]);
}
Output:
Time complexity :
In worst case : Worst case occurs when there are no duplicate values in 'a' array
b[0]= a[0]
i.e, a[1] is present in b array or not --1 comparison as b array contains only one element at that moment
Since there are no duplicate elements in 'a' array then b[1] will contain a[1] i.e, b contains 2 elements now.
then
a[2] is checked if it is present in b[0] or b[1]---doing 2 comparisons
a[3] is checked if it is present in b[0] or b[1] or b[2]---doing 3 comparisons
:
:
a[n-1] is checked if it is present in b[0] or b[1] or......b[n-2] --- doing n-1 comparisons
adding all the comparisons
1+2+3+....n-1 .
this is nothing but sum of first n-1 natural number i.e, = ((n-1)*(n-2))/2 = n^2
Hence Time complexity of above program is O(n^2)
In Best Case: occurs when all the array elements in 'a' array are same
b[0]=a[0]
a[1] is compared with b[0] for equality ...since a[1] and b[0] are same, b array will contain only one element.....1 comparison is done
a[2] is compared with b[0] for equality ...1 comparison is done
a[3] is compared with b[0] for equality ...1 comparison is done
:
:
a[n-1] is compared with b[0] for equality ...1 comparison is done
Adding all comparisons
1+1+1+......n-1 times.
that is n-1 comparisons
Hence Best Time complexity is 'n'
