6
$\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.

$\endgroup$
  • $\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 Apr 6 '16 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 Apr 6 '16 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 Apr 6 '16 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 Apr 6 '16 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 Apr 6 '16 at 16:57
-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.

$\endgroup$
  • 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 Apr 6 '16 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 Apr 6 '16 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 Apr 6 '16 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 Apr 7 '16 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 Apr 7 '16 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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