CODEWITHSUNDEEP
algorithmbig-o
Takkun
Takkun

Reputation: 6361

O(log n) algorithm for finding max of array?

Does an algorithm exist that finds the maximum of an unsorted array in O(log n) time?

Upvotes: 19

Views: 38617

Answers (12)

Md Yazdan Rizwan
Md Yazdan Rizwan

Reputation: 1

Yes, we can do that, but your array must be a mountain array. Here is an example function:

    public int peakIndexInMountainArray(int[] arr) {
        int s = 0;
        int e = arr.length-1;
        int mid = s+(e-s)/2;
        while(s<e) {
            if(arr[mid] < arr[mid+1]){
                s = mid+1;
            }
            else {
                e = mid;
            }
            mid = s+(e-s)/2;
        }
        return mid;
    }

Upvotes: -1

VadimPlatonov
VadimPlatonov

Reputation: 145

There is an algorithm better than O(N):

You just pick a random element from array and assume it's the largest.

No, seriously, if you have an array of normally distributed numbers, and you need to get not the largest number, but some number close to the largest, then you can, let's say, make N/10 random picks and chose the largest from those. For normal distribution the chances of finding a number close enough to the largest are pretty high. Or you can be lucky and even find the largest, but you won't know for sure if you found it or not.

I think, for some cases this approach may be useful. For example, if you need to group your numbers into buckets but you don't want to read the whole array. In that case you can take random 10% sample and make buckets based on max value of that sample plus one extra bucket for numbers above that 10% max. And that should be good enough.

Upvotes: -1

Abhishek Choudhary
Abhishek Choudhary

Reputation: 399

O(log n) implies you won't even have to read the whole array as that would be O(n), that's not really possible for unsorted array as you can't be assured about an element being maximum if you can't compare it to all other elements. O(n) is the best you can have to get absolute maximum which traverses array only once, if you only want an approximate, you can randomly pick elements and have maximum of them which will pick lesser than n elements, still, O(log n) is just not possible for unsorted array.

Upvotes: -1

ibrahim
ibrahim

Reputation: 35

I think using Segment tree could be helpful , you could achieve log(N) cost .

Upvotes: -2

Franklin Zhao
Franklin Zhao

Reputation: 1

If you use N processors, it can be done in O(log N) time. But the Work Complexity is still O(N).

If using N^2 processors, you can reduce time complexity to O(1) by applying the Usain Bolt algorithm.

Upvotes: -2

alx - recommends codidact
alx - recommends codidact

Reputation: 4527

This is very old, but I don't agree with the answers given. YES, it can be done, with parallel hardware, in logarithmic time.

Time complexity would be:

O(log(n) * log(m))

n is the quantity of numbers to compare; m is the size of each number.

However, hardware size would be:

O(n * m)

The algorithm would be:

  1. Compare numbers in pairs. Time of this is O(log(m)), and size is O(n * m), using carry look-ahead comparators.

  2. Use the result in 1 to multiplex both inputs of 1. Time of this is O(1), and size is O(n * m).

  3. Now you have an array half the initial size; go to step 1. This loop is repeated log(n) times, so total time is O(log(n) * log(m)), and total size is O(n * m).

Adding some more MUXes you can also keep track of the index of the largest number, if you need it, without increasing the complexity of the algorithm.

Upvotes: -2

Hossein
Hossein

Reputation: 11

Of course NOT . suppose that there's still an element which you haven't still compared it with any other element . so there is no guarantee that the element you haven't compared is not the maximum element

and suppose that your comparing graph (vertices for elements and edges for comparing ) has more than one component . in this case you must put an edge (in the best way between maximum of two components).we can see that at n-1 operation MUST be done

Upvotes: 1

oleksii
oleksii

Reputation: 35895

It's not possible to do this in O(log(N)). It is O(N) in the best/worst/average case because one would need to visit every item in the array to determine if it is the larges one or not. Array is unsorted, which means you cannot cut corners.

Even in the case of parallelisation, this cannot be done in O(N), because Big-O notation doesn't care about how many CPU one has or what is the frequency of each CPU. It is abstracted from this specifically to give crude estamate of the problem.

Parallelisation can be neglected because time spent dividing a job can be considered equal to the time of sequential execution. This is due to the reason of constants being disregarded. The following are all the same:

O(N) = O(Const * N) = O(N / Const) = O(N + Const) = O(N - Const)

From the other hand, in practise, divide-and-conquer parallel algorithms can give you some performance benefits, so it may run a little bit faster. Fortunately, Big-O doesn't deal with this fine-grained algorithmic complexity analysis.

Upvotes: 6

David Titarenco
David Titarenco

Reputation: 33386

This question is asked a lot (is this a popular CS homework question or something?) and the answer is always the same: no.

Think about it mathematically. Unless the array is sorted, there is nothing to "cut in half" to give you the log(n) behavior.

Read the question comments for a more in-depth discussion (which is probably way out of the question's scope anyhow).

Upvotes: 27

user555045
user555045

Reputation: 64904

Consider this: without visiting every element, how do you know that some element you haven't visited isn't larger than the largest you have found so far?

Upvotes: 10

Jiri Kremser
Jiri Kremser

Reputation: 12837

No. It's O(n). In the worst case all members of the array have to be visited and compared.

Upvotes: 4

elyashiv
elyashiv

Reputation: 3691

no. you well have to iterate through the array at least once.

Upvotes: 4

Related Questions