Checking sorted-order invariants cheaply

Beginner Asymptotics & empirical timing

Created by Pavel · 29.04.2026 at 19:08 UTC

Monotonicity checks appear in time-series QA (“is this slice non-decreasing?”), in merge routines that assume sorted runs, and in validating that a quantile transform was applied correctly. A single left-to-right pass comparing neighbours is Θ(n) and early-exits on the first violation—cheaper than sorting just to test order.

Do not confuse “check sorted” with “sort”: sorting costs Θ(n log n) comparison sorts; verifying sorted is linear.

For duplicate-tolerant definitions, be explicit: strict < vs <= changes validity of flat segments.

Sorting how-to (when you actually need sort): [1].

Sources

[1]https://docs.python.org/3/howto/sorting.html Return to text

University approvals: 0

Tasks

Question 1

Verifying a list is strictly descending (vals[i] > vals[i+1] for all adjacent pairs) for len(vals) == n uses Θ(?) time in the worst case.

Hint

One pass over adjacent pairs.

O(1)

O(n)

O(n log n)

O(n²)

Question 2

A pipeline assumes daily temperature readings are non-decreasing after cleaning. Before running peak detection, you run a validator. Why linear scan instead of sorted(vals) == vals?

Hint

Sorting to test order is overkill.

sorted==vals is always faster

Linear scan is O(n) and short-circuits; full sort is Ω(n log n)

Python lists cannot be compared elementwise

pandas forbids monotonicity checks

Question 3

is_descending(vals) is True iff every adjacent pair is strictly decreasing (>). Length 0–1 → True.

Hint

Compare each neighbour pair once.

def is_descending(vals):
    pass

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

3 test cases will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Asymptotics & empirical timing
Difficulty: Beginner
Completed: 0 users

Creator

Pavel