Algorithms sorting question need help

[sita]

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?

 

[JeffM]

View attachment 10822
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?

Why is sort time of the order n * log(n) in the sorting variant of the first solution, but log(n) in the second solution?

Is there any difference except in description between the first and second solutions? If so, what is it?

Does the problem even ask for two variants of two solutions?

 

[sita]

Why is sort time of the order n * log(n) in the sorting variant of the first solution, but log(n) in the second solution?

Is there any difference except in description between the first and second solutions? If so, what is it?

Does the problem even ask for two variants of two solutions?

It asks for one solution i am asking which solution is better.

Yes the time complexities.

 

[JeffM]

It asks for one solution i am asking which solution is better.

Yes the time complexities.

You have not answered my questions.

You give solution 1 with and without sort. That is 2 solutions. You give solution 2 with and without sort. That makes 4 (not 2) solutions if indeed there is a flyspeck of difference between solutions 1 and 2 except in wording. And asking you to say what is the difference between solutions 1 and 2 is what I asked you before.

Moreover, you give 2 different estimates of run time for sorting. Why?