7
$\begingroup$

Suppose $A$ is an array of integers, $|A|=n$, $A=\{a_i|1\leq a_i\leq N, i=1\ldots n\}$.

The goal is to find an efficient algorithm $\cal{F}$ to find maximum element in $A$ with these restrictions:

  • $\cal{F}$ should not compare any $a_i$ with any $a_j$ ever.

  • $\cal{F}$ also should not add, subtract or exploit some fancy facts about integers

  • $\cal{F}$ may, however, compare any $a_i$ with some predetermined constant number, and this number may depend on $N$

Why does algorithm exist? Well, counting sort will work, it never compares elements with each other. Its complexity is $O(n+N)$.

I propose this:

compare all $a_i$ with $N/2$, let $L=\{a_i\in A|a_i<\frac{N}{2}\}$, $U=\{a_i\in A|a_i\geq\frac{N}{2}\}$.

If $U$ isn't empty, we may throw $L$ away and compare $U$ with $3N/4$, etc...

If $U$ is empty, we have our initial problem but now the upper bound is $N/2$. Call algorithm recursively.

Basically, it is binary search on $N$, so it will do in $O(n\lceil\log N\rceil)$ in the worst case. If $N$ is big enough it is better than counting sort.

Two questions:

a) am I correct with my algorithm? I can't see any flows in binary search implementation.

b) it is not obvious to me that binary search in this problem is the best solution, is it possible to do better? If not, how to prove it?

I've added some more explanation to clarify the question. According to comments (thanks, EvilJS) I've used term "comparison-based sorting" wrong, so sorry for that.

Improve this question
$\endgroup$
7
  • $\begingroup$ 1) Why this restriction? 2) Why do you think this is possible? 3) When and how do you change the constant to compare with? 4) "upper half if it isn't empty " -- why does that make sense? Do you assume the array is sorted? $\endgroup$
    – Raphael
    Commented Apr 6, 2016 at 15:06
  • $\begingroup$ 2) because I can compare every element of A with every number from 1 to N and that will give the result 3) N is an entry for algorithm, I will compare $a_i$ with N/2, after that with N/4 or 3N/4 etc. 4) I do not need compare anything less than N/2 if there is something more than N/2. It is comparison based so I can't use radix, I can compare elements with numbers but not elements between each other. How it can be $O(n)$? $\endgroup$
    – sas
    Commented Apr 6, 2016 at 15:12
  • 1
    $\begingroup$ So you are doing binary search on N looking for max. It will work since you have bounded N, ok it is $O(nlogn)$, but the description is not very obvious. $\endgroup$
    – Evil
    Commented Apr 6, 2016 at 15:21
  • 1
    $\begingroup$ You might also be interested in cs.princeton.edu/courses/archive/fall13/cos226/lectures/… if you excuse this lighthearted comment. $\endgroup$
    – wvxvw
    Commented Apr 6, 2016 at 15:44
  • $\begingroup$ Counting sort is not a comparison-based algorithm. Can you clarify what your computation model is, exactly? A natural model would be the decision tree model, with allowable queries "$a_i < m$". You are interested in the depth of the shallowest tree. $\endgroup$
    – Yuval Filmus
    Commented Apr 6, 2016 at 16:57

1 Answer 1

Reset to default
-1
$\begingroup$ 
a) am I correct?

No, that's not correct. Suppose this array is an unsorted array, and you want to find a maximum element in this array.

First, sorting this array in the increasing order. You can use mergesort or quicksort to sort the array. Mergesort will guarantee the time complexity in the worst and average cases is O(nlogn). However, quicksort will take O(nlogn) for the average case, and O(n) for the worst case. Regarding the worst case of quicksort, if partitioning the array into two groups which one group is empty and another one is (n-1), this will take O(n) time complexity.

Second, after you have a sorted array in increasing order, you can get the maximum element at the last element in the sorted array. 

b) is it possible to do better?

You can use heapsort with max heaps property. In this case, the largest element is at the root for max heaps. Heapsort will take O(nlogn) since building maxheap takes O(n) and max-heapifying takes O(logn). It takes only O(1) to find a maximum element.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ If the array is not sorted it does not matter - checking whole array for every fixed N will find maximum. Your sorting algorithms are in conntradiction with given constraints. If this was possible, $n - 1$ comparisons would suffice. Quicksort is not linear in the worst case. Disregarding constraints given, sorting to find max value is overkill and performance killer. $\endgroup$
    – Evil
    Commented Apr 6, 2016 at 16:18
  • 1
    $\begingroup$ The OP isn't allowed to compare two elements directly. So they cannot use standard sorting procedures. On the other hand, the algorithm suggested by the OP works. $\endgroup$
    – Yuval Filmus
    Commented Apr 6, 2016 at 16:36
  • $\begingroup$ Well, may be it was unclear that I cannot directly compare $a_i$ due to incorrect usage of terms in original question. I rewrote it, I hope it is better now. $\endgroup$
    – sas
    Commented Apr 6, 2016 at 16:53
  • $\begingroup$ @EvilJS: You are right, since we have to check every element in the array to find the maximum, and the question was originally pretty ambiguous, now it looks better, sas! $\endgroup$
    – Tung Le
    Commented Apr 7, 2016 at 15:17
  • $\begingroup$ It is better now, but whatever reason was behind it seems that your answer is still unfortunately breaking rules given by OP. $\endgroup$
    – Evil
    Commented Apr 7, 2016 at 15:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.