Bitonic

Bitonic is an adjective in mathematics and computer science used to describe sequences that have two monotonic phases. In its common form a bitonic sequence increases up to a single peak and then decreases. The peak may be at the end or the beginning, in which case the sequence is purely increasing or decreasing; such monotone sequences are often treated as degenerate bitonics.

In algorithmic problems, the longest bitonic subsequence problem asks for the longest subsequence of a given sequence that is bitonic. A typical solution computes for each position i the length of the longest increasing subsequence ending at i and the length of the longest decreasing subsequence starting at i, then the maximum of their sum minus one. This yields an O(n^2) dynamic-programming approach; with optimization it can be improved to O(n log n) using LIS variants.

Bitonic sort is a comparison-based sorting algorithm designed for parallel computation. It works by transforming the input into a bitonic sequence (one that increases then decreases) and then recursively merges halves. In parallel, it sorts in O(log^2 n) time with O(n log^2 n) total comparisons; in sequential form, the typical implementation runs in O(n log^2 n) time as well. Bitonic sort networks were introduced by Ken Batcher and are popular in hardware implementations and GPUs due to regular structure and data-parallelism.

The bitonic traveling salesman problem (bitonic TSP) is a classic problem in computational geometry. Given a set of points in the plane with unique x-coordinates, there exists an optimal shortest tour that is bitonic with respect to the x-order. The problem can be solved in O(n^2) time by dynamic programming. The term also appears in other domains where a two-phase monotone pattern is exploited.