1,889 views
3 votes
3 votes
Leading element in an array of n elements is the element which occurs more than n/2 times in the array.

a) What is the time complexity to find whether a leading element exists or not in a sorted array of n elements?

b)What is the time complexity to find whether a leading element exists or not in an array whose range of values are between 0 to n?

c)What is the time complexity to find whether leading element exists or not in an unsorted array of n elements?

1 Answer

1 votes
1 votes

What is the time complexity to find whether leading element exists or not in an unsorted array of n elements?

First we find the majority Element in an array :

I:e

Array :  3  5  3  3  5 3  3  7 3  5

n = 10

int count = 0 ;

int candidate  = 0

     

Integer candidate = null;
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (count == 0) {
                candidate = array[i];
                count = 1;
                continue;
            } else {
                if (candidate == array[i]) {
                    count++;
                } else {
                    count--;
                }
            }
        }
 
 
Explanation :
Iteration 1    : array[0] = 3 ,     candidate = 3    , count = 1 ;
Iteration 2    : array[1] = 5 ,     count - -  , count = 0 , candidate = 3
Iteration 3    : array[2] = 3 ,     candidate = 3 ,  count  = 1
iteration 4    : array[3] = 3 ,     candidate == array[3] // holds true , count++  , count = 2 ,  candidate = 3
iteration 5    : array[4] =  5,     count - - , count = 1 , candidate = 3
iteration 6    : array[5] = 3 ,     candidate == array[5] // holds true , count ++ , count  = 2 , candidate = 3
iteration 7    : array[6] = 3 ,     candidate == array[6] // holds true , count ++ , count = 3 , candidate = 3
iteration 8    : array[7] = 7 ,     count - - , count = 2 ,  candidate = 3
iteration 9    : array[8] = 3 ,     candidate == array[8] // hold true ,  count ++ , count = 3
Iteration 10 : array[9] = 5 ,      count- - ,  count = 2 , candidate = 3
 
we done out execution in which final count = 2 and candidate =  3
which mean candidate = 3  is our majority element which occurs most of the  time
and this required : O(n)
 
Now , we have to check whether it occurs greater then n/2 times or not
 
count = 0;
        for (int i = 0; i < array.length; i++) {
            if (candidate == array[i]) {
                count++;
            }
        }
        return (count > array.length / 2) ? candidate : null;
    }

  it also required : O(n)

 

total time complexity : O(n) + O(n) = O(n)

 

Related questions

4 votes
4 votes
1 answer
2
0 votes
0 votes
1 answer
3
Sambhrant Maurya asked Aug 7, 2018
390 views
If k is a positive constant, then the following divide and conquer recurrence evaluates to?T(n) = k ; n=1T(n) = 3 T (n/2) + kn ;n>1a)T(n)= 3kn2-knb)T(n)=3kn log23 - 2knc...