Thread: Algorithms which approach is faster?

1. Algorithms which approach is faster? Solution 1:

Without sort:
Loop over numbers in array
match each number with K, increment the count if match.
Time complexity: O(n)
With sort:
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.

Solution 2:

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?

2. Re: Algorithms which approach is faster?

I don't really see the difference between solution 1 & 2. The only difference seems to be that you ignore the cost of sorting in solution 2.2. I guess it could make sense if you want to find the count of many different numbers and you don't care about how long it takes to sort the array because it's only done once. Well, in that case O(log n) is better than O(n) so solution 2.2 would be the winner over 2.1.