An element is called frequent if it occurs at least 2n3 time

An element is called frequent if it occurs at least 2n/3 times in an array of size n. For example, if given input [7, 3, 7, 7, 5, 7] your algorithm should return 7 is frequent since it occurs at least 4 times. Given input [1, 5, 2, 3, 6, 6] your algorithm should return No frequent element. Given an unsorted array A of n integers, design an algorithm that determines whether there is a frequent element. For full marks your algorithm should run in O(n) time. For part marks, you can give an O(n log n) or O(n^2) algorithm. You may use any algorithm we saw in class as a subroutine. Write your algorithm below Analyse the running time of your algorithm.

Solution

Solution a)

int main()

{
int my_arr[100], freqency[100];
int n, i, j, counter;

/*
* Read size of array and elements in array
*/
printf(\"Enter size of array: \");
scanf(\"%d\", &n);

printf(\"Enter elements in the array: \");
for(i=0; i<n; i++)
{
scanf(\"%d\", &my_arr[i]);
freqency[i] = -1;
}

/*
* Counts frequency of each element
*/
for(i=0; i<n; i++)
{
counter = 1;
for(j=i+1; j<n; j++)
{
if(my_arr[i]==my_arr[j])
{
counter++;
freqency[j] = 0;
}
}

if(freqency[i]!=0)
{
freqency[i] = counter;
}
}

/*
* check frequency of any element equals to 2n/3
*/
for(i=0; i<n; i++)
{
if(freqency[i]==(2*n)/3)
{
           temp=1
}
      
}
if(temp==1)
return \"frequent element\";
else
   return \"No frequent element\";
}

Solution b)

running time of this algorithm is 0(n²)