5

I had this exercice in an exam which stated:

Find an algorithm which can search for the highest number in an unsorted list and have a Big-Oh complexity of O(log(N)).

The only searching algorithm with a log n complexity that I have found is the binary search algorithm but that one requires my list/array to be sorted.

Is there such an algorithm?

Improve this question
0

4 Answers 4

Reset to default
13

This is a trick question. It has not been stated that the list has N elements. So, you can use a change of variable, and replace N with 2K. Now, solve the problem with a linear algorithm on a list with K elements.

If we assume there are N elements in the list, a possible solution would be to use N parallel computing elements [ CE0 .. CEN ]. In the base case of the algorithm, we let each computing element CEi in [ CEN/2 .. CEN ] compare list values x2i-N and x2i-N+1. Each computing element reports the larger of their two assigned values to CEi/2. The iterative steps of the algorithm is that each computing element CEk that receives two reported values reports the largest to CEk/2. This iterative logic continues until CE0 processes a report from itself. Instead of reporting to itself again, it outputs the result.

If parallel computation is ruled out, then there is no solution to the problem.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Don't understand the downvote. This is a perfectly valid answer.
Note that the parallel algorithm allows us to get to O(log n) time complexity, but the computational complexity is still O(n).
2

No, there is no such algorithms. In a unsorted list, find a highest number require to browse through all elements.

So, no algorithm better than O(n) exists!

Improve this answer

Comments

2

The best one can do is O(n) time in an unsorted array.

But instead of simply looking through the whole list you can apply a partition() routine (from the quicksort algorithm) and instead of recursing on the lower half of the partition you can recurse on the upper half and keep partitioning until the largest element is found. This takes O(n) time.

Check out for detailed explanation:

http://en.wikipedia.org/wiki/Quickselect

How to find the kth largest element in an unsorted array of length n in O(n)?

Hope it helped! :)

Improve this answer

1 Comment

As per the question O(n) is not good enough. A normal linear search would take O(n) time.
0

Ik this is very old, but if I had this question, I would have used the fact that it did not specify that the list is N elements long, meaning it’s valid to make the assumption that the list has 1 element, then a simple line of code like this should work giving you O(1) time complexity,

Answer= list[0]
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.