Loop over numbers in array
match each number with K, increment the count if match.
Time complexity: O(n)
Sort numbers O(nlogn)
Find first and last index of k using binary search 2*logn = O(logn)
Count= last index - first index + 1
Time complexity: O(nlogn)
Here, Without sort approach is always best.
1. traverse whole array and increase count from 0 to +1 every time we encounter the element
so running time will be O(n) for traversal and comparision and O(1) for count increase so finally we have running time of O(n)
2. faster approach:
first sort the array afterwords we can use binary search method to count the occurrences and its running time complexity will be O(log(n))
Which solution would be better from the two?