For result entries the largest required index is , so the bound in part (a)(iii) permits universe size . Check that the chosen universe can itself be expressed as an array length:The loop invariant is that the result prefix contains exactly and the abstraction function of
def recamanBitmap(a: Array[Int]): Unit = {
val n = a.length
if (n == 0) return
val capacity = n.toLong * (n.toLong - 1L) / 2L + 1L
require(capacity <= Int.MaxValue.toLong, "Bitmap universe too large")
val seen = new BitMapSet(capacity.toInt)
a(0) = 0
seen.add(0)
var i = 1
while (i < n) {
val candidate = a(i - 1).toLong - i.toLong
val next =
if (candidate > 0L && !seen.contains(candidate.toInt)) candidate
else a(i - 1).toLong + i.toLong
a(i) = next.toInt
seen.add(a(i))
i += 1
}
}seen is their set of values. The universe bound ensures that each positive candidate being queried and each actual next value is less than capacity; values are nonnegative. Thus the conversions and the restricted add precondition are justified, rather than merely hoped to succeed. At a repeated addition, add returning false is harmless: the set of previously seen values is still updated correctly. The loop variant is . At return every result entry agrees with the original recurrence.The original routine uses auxiliary space and at most membership work. A bitmap with universe size uses extra storage and work in the sequence-generation loop because membership and insertion each take constant time. Here the safe universal bound chooses , so extra storage is for growing .
Initialization must be accounted for separately: creating and clearing a Boolean array of length takes work in the usual array-initialization model. Consequently the complete one-shot routine takes , which is with this conservative universe bound. The faster lookup does not make that quadratic setup disappear. If the bitmap is already initialized, or the analysis explicitly charges only the generation phase, the remaining phase is linear. A tighter known bound on values can reduce the universe cost, but no unproved growth bound is needed here.
A fixed array containing the distinct seen integers needs capacity at most , because at most one new distinct value is introduced per result entry. Its auxiliary space is therefore , rather than the bitmap's universe storage. A size field identifies the occupied prefix; insertion first checks membership, and appends only when absent.
An unsorted occupied prefix needs linear membership scans, giving total work by the same summation as in the original version. Keeping it sorted permits binary search membership in , but inserting a new value can shift entries, so the overall worst-case upper bound remains quadratic. Unlike a bitmap, the space cost depends on the number of stored values rather than their largest possible numerical magnitude. Compared with part (a)(ii), this extra set array also duplicates information already present in the output prefix; its principal benefit is a separate set interface, not an automatic asymptotic speedup.
Articles by others on the same topic
There are currently no matching articles.