17

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

Takkun
  • 6,131
  • 16
  • 52
  • 69
  • Yes: If it's either sorted, or you have a very large number of cores/processors. – Mysticial Sep 15 '12 at 20:31
  • possible duplicate of [How to find maximum value in any range of an array in log(n) time?](http://stackoverflow.com/questions/9467247/how-to-find-maximum-value-in-any-range-of-an-array-in-logn-time) – David Titarenco Sep 15 '12 at 20:32
  • it's not sorted. how can more cores do a so big change? – elyashiv Sep 15 '12 at 20:32
  • 1
    @elyashiv It's called a parallel reduction. Every core/processor starts with the max of a small number of elements, then you do a binary tree reduction. – Mysticial Sep 15 '12 at 20:33
  • @Mysticial: Even with parallel cores, it will be `O(n/k + logk)` at best, and not `O(logn)`. – amit Sep 15 '12 at 20:35
  • 1
    @amit Hence the "very large number of cores/processors". i.e. Such as when `k > n`. – Mysticial Sep 15 '12 at 20:36
  • 2
    @amit using your formula, what happens when n == k? n/n + log(n) = 1 + log(n) = log(n). So, if you have n cores (in actual fact n/2 cores is enough), you can get O( log(n) ). Although you might need to add in a term for the parallelization overhead (latency of communication between processors). – Xantix Sep 15 '12 at 20:39
  • 4
    @Xantix, @Mystical: This is a specific case where the number of cores is *linear* with the number of elements. Traditionally in parallel analysis we have one of two choices: (1) Consider `k` as some constant and thus ignore it. (2) Use the `k` notation explicitly. I have never seen any book/article analyzing an algorithm assuming the number of cores `k = f(n)` for some function `f` (besides constant, of course). If someone did - please reference me to this source and I'll revert my comment. – amit Sep 15 '12 at 20:43
  • 1
    @Mystical, I think thread allocation complexity is still `O(n)`, so you end up with `O(n log n)`. Brent's theorem may help with some algorithm cascading here (the proof is nontrivial), but maybe I've misunderstood the concept. See http://www.uni-graz.at/~haasegu/Lectures/GPU_CUDA/Lit/reduction.pdf slide 30. – David Titarenco Sep 15 '12 at 20:45
  • @amit We're not targeting the usual case. We're trying to find *any* condition, no matter how-farfetched, that could satisfy `O(log(N))`. – Mysticial Sep 15 '12 at 20:46
  • 1
    @DavidTitarenco Not necessarily. If that was the case then current supercomputers (with 100k+ cores) wouldn't be feasible. Resource allocation can be done it parallel. Thread allocation can also be done in a tree-like expansion. – Mysticial Sep 15 '12 at 20:47
  • @Mysticial: care to source that? it's not that I don't believe you, but everywhere I've looked, I always see parallel-time algorithm complexity *defined* as `O(processors × time complexity)`. So even if you have a per-thread logarithmic time complexity, the algorithm itself is not `log(n)` – David Titarenco Sep 15 '12 at 20:52
  • @DavidTitarenco [See if you can access this paper](http://rsim.cs.illinois.edu/arch/qual_papers/systems/3.pdf). I'm not sure if it's public or if it requires authentication from my university. That aside, if we're talking about *computational* complexity. Then yes, you're stuck with `O(N)`. But if it's about `time` complexity, then you could possibly cheat with having a large number of processors. – Mysticial Sep 15 '12 at 21:02
  • Thanks. I can access it and I'll check it out! – David Titarenco Sep 15 '12 at 21:03
  • 1
    @DavidTitarenco: I can't speak as to this sort of case, but I know with Sorting Networks, complexity is explicitly qualified as either the "size" (correlating with `O(#processors x time complexity)` ) or "depth" (correlating with `O(time complexity)` ), so I would extrapolate to this question as the idea that either is correct, if adequitely qualified. http://en.wikipedia.org/wiki/Sorting_network – Mooing Duck May 14 '14 at 18:59

11 Answers11

26

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).

David Titarenco
  • 32,662
  • 13
  • 66
  • 111
10

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?

harold
  • 61,398
  • 6
  • 86
  • 164
6

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.

oleksii
  • 35,458
  • 16
  • 93
  • 163
  • Big O analysis certainly deals with divide and conquer complexity. And if your parallelism is n/2 comparisons simultaneously then it reduces to O(log n) complexity. And the fine grained points are totally irrelevant if n is large enough and you actually had such an absurdly large number of processors. You would get practical time savings. Dividing the job is potentially a one time task, while the computation could be repeated many times. It's not particularly realistic to have huge numbers of dedicated processors waiting to solely do this task, but its theoretically and practically posible – Gregory Morse Feb 15 '21 at 01:51
  • @GregoryMorse assuming it is possible to have an N-Core supercomputer. One can assume that it is possible to divide the task between every core. So that each core executes some computation task. Which *would* make this is an `O(1)` task, only if we didn't have to *then* conquer - compare the computation between each other to figure out the largest of the computed values. Comparison is `O(1)` operation, but it needs to be repeated `N` times, as there is no way to not-compare something and still get a max value. Thus `O(log n)` is impossible for this task, irrespective of a number of cores. – oleksii Feb 15 '21 at 15:54
  • This is incorrect the conquer part is O(log n) steps. The tournament winner style algorithm means each step half as many comparisons are needed. So first compare n/2 in O(1) then n/4 in O(1) ... until 1 remains, the max. It's the archetypal log n algo – Gregory Morse Feb 16 '21 at 16:14
  • The problem is, the array is *not sorted*. If it was a sorted array then one could try using something like this, but then the first (last) element would provide the result in `O(1)`. How would this idea work on `4, 1, 0, 22, 7, 3, 5`, what if I move `22` to the first/last place? This logic cannot be applied to unsorted data. – oleksii Feb 16 '21 at 17:07
  • Actually the tournament algorithm applies EXACTLY to unsorted arrays. [4, 1, 0, 22, 7, 3, 5] -> [4, 22, 7, 5] -> [22, 7], -> [22]. It doesnt matter where it is. [22, 4, 1, 0, 7, 3, 5] -> [22, 1, 7, 5] -> [22, 7] -> [22]. [4, 1, 0, 7, 3, 5, 22] -> [4, 7, 5, 22] -> [7, 22] -> [22]. I suggest taking a formal algorithms course. It is where I learned about this. The odd number at any stage is a "by" to the next round of a tournament - just a ceiling function ultimately in the recurrence relation. Remember we are talking about parallelism here!!! Of course this is right for the non-parallel – Gregory Morse Feb 22 '21 at 18:14
  • 1
    @GregoryMorse One cannot simply use tournament selection here, as one needs to build tournaments first. Building tournaments is an O(n). I am happy to leave it here: you think you are right, so be it. – oleksii Feb 22 '21 at 20:46
  • Yes, I suppose I am talking about comparison steps being O(log n). Distribution of work for divide and conquer is a separate problem. A dedicated parallel system can distribute work in O(1)... Practically speaking constructing the parallel system will be O(n) but its a one-time cost if its reused. Anyway what has interested me most is analyzing comparisons. Certainly thats not the only thing at play here though. – Gregory Morse Feb 23 '21 at 12:12
4

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

elyashiv
  • 3,623
  • 2
  • 29
  • 52
4

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

Jiri Kremser
  • 12,471
  • 7
  • 45
  • 72
1

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

Hossein
  • 11
  • 1
0

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.

Abhishek Choudhary
  • 343
  • 6
  • 16
0

Yes, we can do that but with the condition, If our array is a mountain array. `

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;
}`
Md Yazdan Rizwan
  • 1
-1

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.

alx - recommends codidact
  • 4,204
  • 3
  • 22
  • 51
-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.

Tim Diekmann
  • 7,755
  • 11
  • 41
  • 69
Franklin Zhao
  • 1
  • 1
-1

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

ibrahim
  • 37
  • 8