Ace Algorithms

Question

Suppose A  is a sorted array and some of the elements are duplicates.  What is the best upper bound to find out the number of elements that are equal to a given key 'k'

a) O(log n)

b) O(n)

c) O(nlogn)

d) O(n2)

Comments

i am getting O(n). as we have to go to left and right sides to find the locations to which key k is present in worst case...

t(n)= t(n/2)+t(n/2)+ constant

O(n)...

maybe we can convert it to logn but i am confused.

---

We will use Binary search to find the index of first && Last  occurence of  "K". In O(Log n).So answer should be Option a)

Answer 1

The answer should be O(n). In the worst case even if we go by linear search then to find the number of times the duplicate key is present then also it would take O(n) as the array would be traversed once.

if we use Binary search then after the particular key element that we are searching for is found we have to go both in the left and the right direction to count the no. of duplicate elements. So it will require additional time in comparison to O(logn).

Comments

but binary search wont work here see if all the elements are duplicate then in first go we will find that element ,now for searching all the duplicated it will take O(n) time since all the elements are duplicate.

correct me if i am wrong

---

ya .. that is why the time complexity would be O(n) and not O(logn).. In the nas I have written that if binary search is used additional time would be required again for going in both the directions..