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$
$\endgroup$
1
-
$\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$– NobodyAug 21, 2018 at 13:18
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
9
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".)
answered Aug 21, 2018 at 14:59
-
2$\begingroup$ Agreed (+1) up until the last paragraph. Does positive really ever mean anything other than "strictly positive"? $\endgroup$– wcharginAug 22, 2018 at 0:14
-
1$\begingroup$ @wchargin codegolf.meta.stackexchange.com/questions/1324/… $\endgroup$– user92772Aug 22, 2018 at 0:22
-
$\begingroup$ @user202729 codegolf.meta.stackexchange.com/questions/1324/… :-) (but thanks for the link) $\endgroup$– wcharginAug 22, 2018 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, 2018 at 8:23
-
$\begingroup$ @Apass.Jack I'm not bowing to anything; I'm noting usage. $\endgroup$ Aug 22, 2018 at 8:55