2
$\begingroup$

Could someone explain the following question -

Given the following statement viz. Consider an input array a[1..n] of arbitrary numbers. It is given that the array has only O(1) distinct elements. What does the statement imply ?

Thanks.

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Aug 25 at 20:02
  • 1
    $\begingroup$ It's not clear whether you're looking for what it means or what it implies. The given answer says what the statement that the array has O(1) distinct elements means; but one thing that it implies, for instance, is that some element appears O(n) times. There are various other implications, too; for instance, it can be sorted in time O(n), etc. Can you be at all more specific about what you're after? $\endgroup$ – Steven Stadnicki Aug 28 at 22:51
  • $\begingroup$ I guess what I was looking for is that O(1) distinct elements in an array implies that there would be a fixed number of distinct elements, no matter the size of the array(n). $\endgroup$ – parthdt Aug 30 at 14:30
1
$\begingroup$

Essentially, it means no matter what the size of the array is (namely, no matter what $n$ is), it will have no more than a fixed constant number of distinct elements. This assumes that you know what the term $O(1)$ means. If not, ask for clarification.

$\endgroup$
  • $\begingroup$ In addition to this, is it possible to sort this array with O(1) distinct elements with O(n) time complexity? $\endgroup$ – parthdt Sep 3 at 16:42

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.