(definition)

**Definition:**
An *algorithm* whose behavior, by design, is independent of some property that influences a typical algorithm for the same problem.

**Generalization** (I am a kind of ...)

*algorithm*.

**Specialization** (... is a kind of me.)

*bitonic sort*.

*Note:
For example, an oblivious sort algorithm always makes the same comparisons, regardless of the input. This is useful for external sorts, since there is a fixed I/O schedule, or parallel algorithms, like bitonic sort. *

* Other types of oblivious algorithms are cache oblivious, which are not dependent on hardware parameters like cache size and cache-line length, and oblivious routing, which route packets independent of the network topology, the history of traffic flow, or the congestion.*

Author: PEB

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 8 March 2021.

HTML page formatted Mon Mar 8 10:01:45 2021.

Cite this as:

Paul E. Black, "oblivious algorithm", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 8 March 2021. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/obliviousAlgorithm.html