Why do we consider the sequence "3,3,4,5,2" a bitonic sequence?

In the sequence, "3,3,4,5,2", the sequence is

  • constant for "3,3",
  • increasing for "4,5", and
  • decreasing for "5,2".
  • $\begingroup$ According to this site: A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing. , your example might be incorrect because "3,3" is not strictly increasing. I am not an expert. Waiting for experts to explain. $\endgroup$ – scaaahu Aug 21 '18 at 13:18

Bitonic sequence is defined for example for parallel sort, as non-decreasing and then non-increasing sequence, to allow duplicates.

See here: Bitonic sequence. Also Wikipedia article about Bitonic sorter shows the same definition which is, afaik, the common one.


The words "increasing" and "decreasing" are used in inconsistent ways. Probably, you're assuming one definition while the author of the text that's confusing you is using the other. Say that the sequence $a_1, \dots, a_n$ is

  • type A if $a_1\leq a_2\leq \dots\leq a_n$;
  • type B if $a_1<a_2<\dots<a_n$.

The problem is that

  • some people refer to type A sequences as "nondecreasing" and type B sequences as "strictly increasing", which is unambiguous;
  • some people call type A "nondecreasing" and type B "increasing";
  • some people call type A "increasing" and type B "strictly increasing".

This means that the term "increasing" is ambiguous because some people use it for type A and some people use it for type B. (And ditto for variants of "decreasing".)

The same problem occurs, though to a much smaller extent; with the terms "nonnegative", "positive" and "strictly positive": the first definitely means $\geq 0$, the last definitely means $>0$; the majority of people use "positive" to mean $>0$ but a few use it for $\geq 0$. (And ditto for variants of "negative".)

  • 2
    $\begingroup$ Agreed (+1) up until the last paragraph. Does positive really ever mean anything other than "strictly positive"? $\endgroup$ – wchargin Aug 22 '18 at 0:14
  • 1
    $\begingroup$ @wchargin codegolf.meta.stackexchange.com/questions/1324/… $\endgroup$ – user92772 Aug 22 '18 at 0:22
  • $\begingroup$ @user202729 codegolf.meta.stackexchange.com/questions/1324/… :-) (but thanks for the link) $\endgroup$ – wchargin Aug 22 '18 at 8:11
  • 2
    $\begingroup$ I agree with @wchargin and I would like this site to not to bow to France's bad usage. I strongly advise against saying that the same problem occurs with the terms "positive" and "negative", especially when we are in a site whose name contains "computer science". At the very least, could you add a word or two to discourage the ambiguous usage of positive thats include 0 and the usage of negative thats include 0? $\endgroup$ – John L. Aug 22 '18 at 8:23
  • $\begingroup$ @Apass.Jack I'm not bowing to anything; I'm noting usage. $\endgroup$ – David Richerby Aug 22 '18 at 8:55

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.