Why is a byte offset into UTF-8 O(1) but a character offset not?

## Where O(1) random access comes from Array indexing is constant time for one reason: the address of element `i` is `base + i * width`, and that arithmetic does not depend on `i` or on the data. Every fixed-width structure inherits it; nothing variable-width does. UTF-8 stores a code point in one to four bytes, chosen by the code point's magnitude. There is no multiplication that answers "where does code point 5000 begin?" — the answer depends on every byte before it. So: - **Byte offset:** O(1). Bytes are the fixed-width element. - **Code-point offset:** O(n). You must decode forward, counting lead bytes. - **Grapheme-cluster offset:** O(n), with a larger constant, since clustering rules need lookahead. This is not a defect of UTF-8. It is the price of compactness, and it is the same trade a linked structure makes against an array: you buy something (ASCII costs one byte, the encoding is ASCII-compatible and byte-order independent) and you pay in random access. ## The gift UTF-8 does give you: self-synchronization UTF-8's byte patterns are unambiguous by construction. A lead byte starts with `0`, `110`, `1110` or `11110`; every continuation byte starts with `10`. So from *any* byte in the middle of a buffer you can tell whether you are at a boundary, and if not, walk backwards at most three bytes to find one. That is O(1), with a bound of three, independent of document size. This is a bigger deal than it looks. It means: - An arbitrary byte offset — from a chunked reader, a memory-mapped scan, a random seek — can be snapped to a valid boundary cheaply. - Corruption or a lost byte damages one character, not the remainder of the stream; the decoder resynchronizes on the next lead byte. - Parallel processing works: split the buffer at arbitrary offsets, snap each split to a boundary, process the chunks independently. What self-synchronization does **not** buy is counting. "Which byte is the 5000th character?" still requires a scan. Distinguishing these two — cheap boundary *alignment* versus expensive ordinal *counting* — is the point of the question. ## How real systems cope There are four standard moves, and the useful answer names the tradeoff of each. 1. **Expose byte offsets and document the unit.** Cheapest and most honest. A search service that returns "match at bytes 1200–1240" is precise and O(1) to apply. The cost is that the unit leaks into the API contract, so every client must agree — and a client that slices at those offsets in a different unit reintroduces the boundary bug. 2. **Keep a sparse offset index.** Record the byte offset of every 1024th character. Seeking to character `k` becomes a lookup plus a bounded scan of at most 1024 characters — effectively constant for a fixed stride, at the cost of memory proportional to length/stride and of maintenance on every edit. 3. **Hand out cursors, not integers.** An opaque position object that carries its byte offset and can step forward or back in O(1) amortized. This removes the whole class of "index in the wrong unit" bug, at the cost of a less convenient API. 4. **Change the representation.** A fixed-width four-bytes-per-code-point buffer restores O(1) code-point access — and quadruples memory for ASCII, which is why almost nothing uses it for storage. Editors typically reach for a rope or piece table with cached line and offset metadata instead, which gives near-constant seeks while keeping edits cheap. ## The trap: UTF-16 looks safe and is not UTF-16 tempts teams because its units are uniform *for the Basic Multilingual Plane*, which covers every character in most test corpora. Index arithmetic appears to work. Then a code point above U+FFFF arrives as a surrogate pair, ordinals and units drift apart, and the same O(n) counting problem appears — now as a rare, data-dependent bug rather than an obvious property of the format. Ecosystems split on this: some expose text as UTF-8 bytes, others as UTF-16 code units, others as code points, so "the index is O(1)" can be true, false or true-but-not-of-characters depending on the runtime, and a position handed across a boundary between two of them is only meaningful with its unit attached. ## What a strong answer contains Start from why fixed width is what makes indexing constant. State the three costs (byte O(1), code point O(n), cluster O(n)). Add self-synchronization and be precise that it buys alignment, not counting. Then pick a coping strategy for a stated workload — byte offsets in a protocol, a sparse index for a large read-mostly document, cursors for an editing surface — and name what each one costs. The judgment on display is not knowing the encoding; it is refusing to promise O(1) on a unit that cannot deliver it.