Made Easy Algorithms

Question

How to calculate the time complexity for finding repeated elements in an array of n elements using linear search and binary search?

Answer 1

using linear search

approach 1: if input data elem range is defined

eg if all char then we can make an arr char of size 26. ie. we can use bool array/hasing/negate the value

 

approach 2: if size is not defined then we can use bst each node have two fields data and freq.

aporoach3: first sort the input array

for i=0 to n{

    int j=i;

      while(a[i]==a[i+1]){

               i++

    }

   if(j!=i)

     print a[j];

}

Using Binary Search:

first sort the input array for everi a[i] apply binary search.

Comments

if range is not given then time complexity is O(nlogn).?????