Just have to look once in the middle item that's all.In a sorted array it must be in the middle by given condition that it must occur n/2 times of the array,hence O(1). Why to look other indices?

Dark Mode

Sambhrant Maurya
asked
in Algorithms
Aug 7, 2018

1,286 views
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?

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?

0

IN SORTED ARRAYS

He's saying that .. If the leading element X which occurs n/2 times.

Then it should be there at the position n/2.

Position : 1 2 3 4 5 6 7.... n/2 ..... n

Element : n/2 times So, from (1 to n/2) or (2 to n/2 +1) or (n/2 to n) ..

If we check the middle element we can easily find out ...

He's saying that .. If the leading element X which occurs n/2 times.

Then it should be there at the position n/2.

Position : 1 2 3 4 5 6 7.... n/2 ..... n

Element : n/2 times So, from (1 to n/2) or (2 to n/2 +1) or (n/2 to n) ..

If we check the middle element we can easily find out ...

0

1 vote

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)