While studying the book "Introduction to Algorithms by Cormen", I found a strange thing. Everywhere if it refers to an increasing order, the book refers it as "non-decreasing" order.. I mean, if a series (2,5,6,3) is to be arranged in "non-decreasing" order.. is'nt it already right?? or "increasing" and "non-decreasing" words mean one and the same?
8 Answers
Increasing - 1 2 3 4
Nondecreasing - 1 1 2 3
The difference being that in an increasing sequence, for x(n) and x(n+1), x(n+1) > x(n) whereas in a non-decreasing sequence, x(n+1) >= x(n)
1,2,3,4 is an increasing sequence or a non-decreasing sequence.
1,1,1,1 is a non-decreasing sequence but isn't an increasing sequence.
Increasing means that every element is greater than the one before it. Non-decreasing means that no element is less than the element before it, or in other words: that every element is greater than or equal to the one before it.
If there are duplicates in the series, then the term "non-decreasing" is more accurate that "increasing."
It depends on the way the author defines these terms.
In your case the authors distinguish non-decreasing (1, 2, 2, 3) and increasing (1, 2, 3). This makes sense in the context of a total order, where not a > b implies a <= b.
Other people call this increasing (1, 2, 2, 3) and strictly increasing (1, 2, 3). This makes more sense in the context of a partial order, where for two distinct elements a and b it may be the case that neither a < b nor b < a holds.
Non-decreasing means exactly that. It's not quite the same as increasing, since it does not tell you what to do with identical values.
Consider the sequence 1, 2, 2, 3, 4 . It's a non-decreasing sequence because the values are in order, yet do not strictly increase from value to value ( ie, 2 is not greater than 2).
The series can be increasing and decreasing as others already explained but can also be non of them.
(1,3,2,4,5,9,1,0)
Is neither decreasing nor increasing. However, there are subsets like 2,4,5,9 that are increasing or 9,1,0 decreasing
Related