In-Place Algorithm¶

An algorithm that replaces its designated input with the result while using only a constant number of auxiliary units under a stated memory model.

Version: v1 · 2026-10-17 · History
Domain-specific #: 14188
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Space Efficient Algorithms → Computer Science & Software Engineering

Core Idea¶

An in-place algorithm, in the strict subset used here, transforms data so that the result occupies its designated input storage while the procedure uses only a constant number of counted auxiliary units. The unit and cost model must be stated: a constant number of array indices uses O(log n) bits for an n-element array, whereas a constant number of ring elements is a different algebraic-space statement. The two bounds cannot be equated without saying how large a ring element is.^[1]^[2]

Both conditions matter. A procedure can return a result at the input address after allocating a full temporary array, or use constant extra storage while writing into a distinct output array. Neither belongs to this strict same-buffer, fixed-unit subset. Wider literature sometimes uses “in place” with looser auxiliary-space bounds; that usage should be identified rather than silently merged into the strict core.^[1]^[2]^[3]

Structural Signature¶

Sig role-phrases: specified transformation and input buffer; same-storage result; declared auxiliary-space model; constant auxiliary-unit budget; overwrite and dependency schedule.

Specified transformation and input buffer. An array or coefficient buffer contains the input whose transformed result is required. Without a designated transformation and carrier, there is no same-buffer question to decide.^[1]^[2]
Same-storage result. The result replaces the specified input rather than occupying a separate full-size output array. A constant-space procedure with a separate output fails this role.^[2]
Declared auxiliary-space model. The account says which indices, pointers, elements, stacks, tables and scratch buffers are counted. A bare “constant memory” claim cannot be compared across computational models.^[1]^[2]
Constant auxiliary-unit budget. In the admitted strict core, the number of such units does not grow with input length. The size in bits of one unit still depends on the stated model.^[1]^[2]
Overwrite and dependency schedule. The operations preserve values needed later until their dependent outputs can be formed, or recompute information within the budget. The particular schedule varies between a permutation and an arithmetic transform.^[1]^[2]

The signature describes an algorithmic resource constraint, not a promise of a particular running time or a universal method such as swapping.

What It Is Not¶

Same-address output alone is insufficient. The FFTW 2 manual says an FFTW_IN_PLACE plan can allocate a temporary array, calculate out of place and copy the result back. That contract puts the final answer in the caller's input array but does not establish constant auxiliary storage for the computation.^[3]

Constant auxiliary space alone is insufficient. Harvey and Roche explicitly classify their polynomial-multiplication application as out of place: its input and output arrays are separate even though the auxiliary ring-element and pointer count is O(1). Their forward truncated Fourier transform, by contrast, overwrites its one coefficient buffer.^[2]

The phrase also does not mean In Situ, whose native-context relation concerns an object or process in its original setting. Sharing the ordinary-language phrase “in place” does not supply an algorithmic output buffer or memory bound. And “in place” in a looser algorithmic paper may allow a growing number of auxiliary units; the strict subtype here must not be treated as the only accepted usage.^[1]

Scope of Application¶

This entry covers transformation algorithms whose result can occupy designated input storage under an explicit, constant-unit auxiliary bound. The two original cases below lie within computer science but use different operations and resource units.

Array rearrangement. Dudek, Gawrychowski and Pokorski study permuting an n-element array by a supplied permutation. Cycle-based schedules rearrange values in that array while avoiding a second n-element array. Their strict model allows only a constant number of input-size indices, hence O(log n) additional bits; restrictions on how the permutation is accessed matter to the algorithm.^[1]
Algebraic transform. Harvey and Roche give a forward truncated Fourier transform that overwrites an n-element coefficient buffer using O(1) auxiliary ring elements and pointers under their stated algebraic model. Their ring and root assumptions matter, and this is not a general bit-space claim.^[2]

The two cases demonstrate the common structural constraint without saying that every sorting, signal-processing or matrix algorithm is in place. Classification requires inspecting its actual storage and model.

Clarity¶

Imagine an array permutation with a fresh n-element destination array. It can be easy to preserve each input value while filling the destination, but the fresh array grows with n. A cycle-based same-array schedule avoids that destination by moving values through the existing array and recognizing which cycles have been handled. Under the cited strict permutation model, only a constant count of indices can be kept outside the array. The cycle-leader technique is a method for that case, not a universal ingredient of every in-place algorithm.^[1]

Now imagine an API that returns the transformed values in the caller's original address. If it first computes into a temporary n-element array and copies back, the storage accounting has changed even though the returned address has not. FFTW 2 documents precisely that possibility. The question is therefore how the computation used memory, not merely where the result was observed at the end.^[3]

Manages Complexity¶

The five-role test separates three questions that are often collapsed into one label: Where is the result? What auxiliary objects are counted? How many are used as n grows? A fourth question checks whether overwrites preserve what the remaining steps need. A named “in-place” option or an O(1) statement answers at most part of this test.^[2]^[3]

This decomposition also prevents a false conversion of units. For the permutation paper, a constant number of indices yields O(log n) extra bits. For the transform paper, O(1) ring elements and bounded pointers are counted as algebraic units. Neither paper makes an unqualified claim that both implementations use the same number of machine bits.^[1]^[2]

Abstract Reasoning¶

To classify a proposed transformation, first name the input region and the required output. Check that the output replaces that region rather than appearing in an independent result buffer. Then inventory every scratch array, stack frame, table, index, pointer and stored element outside the designated region. Declare the size unit, prove that the number of counted units stays constant with n, and inspect the schedule that keeps necessary values available as positions are overwritten.^[1]^[2]

The last step is conditional. The permutation paper's cycle handling works under its assumptions about access to the permutation. The transform paper uses arithmetic dependencies, root generation and an iterative path under its ring assumptions. An algorithm can satisfy the abstract roles with a different valid schedule; it need not look like either of these procedures.^[1]^[2]

Knowledge Transfer¶

The same diagnostic transfers from array permutation to the truncated Fourier transform: identify the buffer that is both input and result, count auxiliary units in the chosen model, then explain why writing the result does not destroy values needed later. It transfers the questions, not the specific cycle-leader or arithmetic operations.^[1]^[2]

It does not license a cross-domain Prime from the word “place.” The defining objects here are algorithmic buffers, output placement and computational storage. An observation made in its original physical or social setting lacks those roles even if an English description calls it in situ.

Examples¶

Canonical: Strict array permutation¶

Dudek, Gawrychowski and Pokorski consider rearranging an array according to a permutation without a second output array. They describe cycle-based movement and the difficulty of recognizing processed cycles when the permutation is not simply marked or overwritten. Their strict algorithms use a constant number of indices, which is O(log n) additional bits in this n-element-index model. A naive cycle-leader method can take quadratic time; their contribution obtains a subquadratic bound for every fixed positive epsilon under the paper's assumptions.^[1]

Mapped back: the transformation and buffer are the specified rearrangement and array; the same-storage result is the rearranged array; the model counts input-size indices and their bits; the budget is a constant index count; the schedule moves values by cycles while recognizing which cycles to process without a growing visited-mark array. This is one cited family of methods, not a requirement that every strict in-place algorithm use cycles.

Applied/practice: In-place truncated Fourier transform¶

Harvey and Roche present a forward truncated Fourier transform that overwrites an n-element coefficient array with n transform outputs. Their computational model counts auxiliary ring elements and pointers outside that one buffer; the algorithm uses O(1) of those units and O(n log n) ring/pointer operations. Its path through transform dependencies and its on-the-fly handling of roots avoid a separate growing table in the stated model.^[2]

Mapped back: the transformation and buffer are the forward transform and coefficient array; the same-storage result is its overwritten transform values; the model counts ring elements and pointers; the budget is O(1) such units; the schedule orders arithmetic so the result can replace coefficients without a full scratch array. The model's ring/root conditions and element-size limits remain attached to this example.

Structural Tensions¶

T1: Strict auxiliary-space budget versus available time bounds in a given permutation problem. Dudek and colleagues contrast a simple constant-index, quadratic-time cycle method with a faster earlier method using more bits; they then construct a strict-space, subquadratic algorithm. The pressure is real for the particular permutation task because fewer retained indices constrain how cycle leaders can be recognized. Their result also prevents a blanket claim that strict space always forces quadratic time. Diagnostic: Under the specified permutation access model, which auxiliary bit bound is required, and which proved running-time bound remains acceptable?^[1]

Same-address API behavior versus actual storage is a diagnostic boundary, not a second structural tension. Nor do these sources establish that every in-place algorithm loses parallelism or runs more slowly.

Structural–Framed Character¶

Structural or framed? The same-buffer result and fixed counted-unit bound give a stable relation across the permutation and transform cases. The unit model and permission to overwrite particular regions frame the exact claim. An O(1) ring-element result is not automatically an O(log n)-bit result.^[1]^[2]

Evaluative weight. Calling an algorithm in place reports a resource and output-location property, not overall superiority. Time, readability, numerical behavior and ease of proof must be evaluated for the particular algorithm. The cited permutation tradeoff does not establish a universal cost.^[1]

Human practice. Authors declare computational models; implementers choose how to satisfy user-visible buffer contracts. FFTW 2 illustrates why an interface promise about output location can differ from a proof about work storage. The useful classification depends on reading both the algorithm and the accounting convention.^[3]

Institutional origin. The strict storage relation is a resource definition in algorithm theory. Neither an FFTW interface nor a particular institution makes an algorithm in place; the operation and its declared memory model do.

Vocabulary travel. “In-place” can be used broadly for small extra storage, narrowly for the strict subset here, or operationally for an API whose final answer reuses an address. State which use is intended. The first two concern algorithms under models; the API use can hide a growing buffer.^[1]^[3]

Import versus recognition. A new permutation or transform belongs to this strict subtype when its same-buffer result and constant counted-unit budget can be established under its model. Calling an observation “in place” because it remains at its native site imports an ordinary phrase without those computational roles.

Underlying relation. Algorithm names a more general kind of procedure. This entry adds a particular output-storage and auxiliary-resource constraint on such a procedure. The constraint is still within computation rather than an unrestricted cross-domain structure.

Its character: a model-framed algorithmic structure. Same-buffer replacement and constant counted auxiliary units remain recognizable across cases, while the model specifies what that statement means.

Structural Core vs. Domain Accent¶

The core skeleton is a transformation whose result replaces its designated input and whose auxiliary-unit count remains constant under an explicit model. The schedule must respect dependencies while the input is rewritten. Remove the output-location condition and Harvey and Roche's separate-output multiplication becomes a false positive; remove the auxiliary bound and the FFTW 2 temporary-array path becomes a false positive.^[2]^[3]

The domain accent is computational: array slots, indices, ring elements, pointer units, algorithmic time and space complexity, and proof assumptions about access and overwrite. Cycle leaders and truncated Fourier butterflies are different case-specific ways to meet the skeleton. Neither is part of its universal mechanism.

The Prime bar is not crossed by the portable-sounding phrase “work where the input is.” Beyond computing, that phrase loses the specified output buffer and complexity accounting. The live Prime Algorithm is the appropriate general bridge; the present strict storage subtype retains its computer-science differentia.

This entry is a kind of Algorithm.

An in-place algorithm is an Algorithm with additional storage constraints. The two cases give ordered, effective transformations with a defined result, while the same-buffer and constant auxiliary-unit conditions distinguish this subtype from algorithms generally. The resource and output-placement restrictions distinguish this subtype from the general procedure.

In Situ is a lexical neighbor, not an asserted parent. Its native-setting relation does not require an algorithmic transformation or a counted auxiliary-memory model. In-Place Adjacent Block Rotation fixes the more specific AB-to-BA positional task with constant auxiliary storage. That operation is a narrower algorithmic case; its particular rotation target cannot define every in-place algorithm.

Relationships to Other Abstractions¶

Current abstraction In-Place Algorithm Domain-specific

Parents (1) — more general patterns this builds on

In-Place Algorithm is a kind of Algorithm Prime

A strict in-place algorithm is an algorithm distinguished by same-buffer output and a constant counted auxiliary-unit budget.

Hierarchy path (1) — routes to 1 parentless root

In-Place Algorithm → Algorithm → Function (Mapping)

Neighborhood in Abstraction Space¶

In-Place Algorithm sits in a sparse region of the domain-specific corpus (63^rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Program Execution & Runtime Concepts (34 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-17

Not to Be Confused With¶

Out-of-place computation writes to a distinct output array, even if it keeps only O(1) additional auxiliary units beyond its designated input and output; the cited polynomial multiplication is an explicit example.^[2] Copy-back execution returns a result in the original address after using a temporary array; FFTW 2 documents this possibility for its named option.^[3] Looser in-place usage permits some growing extra-space bounds and should carry its actual unit and bound. In situ concerns an original context rather than the memory behavior of a transformation. None of these distinctions can be settled by a name or flag alone.

References¶

[1] Bartłomiej Dudek, Paweł Gawrychowski and Karol Pokorski, Strictly In-Place Algorithms for Permuting and Inverting Permutations, 2021, abstract and Introduction, PDF pp. 1–3. Original algorithm paper; strict O(log n)-bit/constant-index definition, cycle methods, access assumptions and problem-bounded time comparison. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r

[2] David Harvey and Daniel S. Roche, An in-place truncated Fourier transform and applications to polynomial multiplication, 2010, §§1.3, 2.1, 3 and 6, PDF pp. 2–5. Original algorithm paper; one-buffer versus separate-output definitions, ring-element/pointer model, transform and multiplication boundary. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r

[3] FFTW project, FFTW 2 Reference Manual, “Plan Creation,” FFTW_IN_PLACE option. Original software manual; documented temporary-array fallback for the FFTW 2 API. No inference about other versions. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h