Worst-Case Complexity of Shellsort with Tokuda's Gap Sequence
Shellsort's worst-case running time is unknown for the gap sequences actually used in practice. Encoding a permutation as the polynomial gives a framework for lower bounds, and yields for Tokuda's 1992 sequence, extending to any strictly decreasing sequence staying within a fixed distance of a rational geometric one.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-assisted
- Method
- Argument
- Field
- Analysis of algorithms
- Posed by
- Donald Shell; Naoyuki Tokuda
- Year posed
- 1992
- Years open
- 34y
- Solved
- 2026-07-10
- Model
- ChatGPT
- Vendor
- OpenAI
- Collaborators
- Zhenghan Zang
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
a lower bound for Tokuda's sequence; the general Shellsort complexity question stays open
What the AI did
The acknowledgement credits the model with providing the initial framework of the proof of Lemma 2, which the author then verified, refined and wrote up.
Verification
Single-author arXiv preprint; not yet peer-reviewed.
Source
arXiv:2607.08997 - Improved lower bounds of the time complexity of shellsort