The relevant quantity is the hash-table load factor , where is the number of distinct keys and the bucket count. With a suitable distribution of hashes, separate chaining has expected operation cost , treating key operations as constant-cost. Keeping only one hundred buckets while grows therefore increases average search length.
Balanced binary search trees could reduce a bucket search from linear time in its occupancy to logarithmic time. Unbalanced binary search trees provide no such guarantee: insertion order can produce a chain. Even balanced trees add comparison and node-management overhead, which may dominate for small buckets.
A usual first remedy is grow the table and rehash its entries, keeping the load factor bounded. Geometric growth gives amortized constant resizing overhead per insertion; with suitable hashing, expected lookup, update and insertion costs remain constant. Resizing is when performed and is not a worst-case constant-time guarantee for that particular operation. Balanced buckets can still be useful for heavy or adversarial collisions, but replacing every bucket tree does not by itself repair a poor hash function. For variable-length strings, hashing and string comparisons add their own character-processing costs.
Find the entry once and check the abstract membership precondition on that result:
def recall(name: String): String = {
  val entry = find(name, table(hash(name)))
  require(entry != null, "name is not in the book")
  entry.number
}
The check turns an invalid call into an explicit precondition failure rather than an accidental null dereference or an invented default number. For a valid call, the unique matching entry contains exactly the mapped value, so the stored number is returned and the map is unchanged. Testing membership by calling isInBook first would traverse the same bucket twice; retaining the found reference avoids that redundant work.
Membership is exactly whether the bucket search finds an entry:
def isInBook(name: String): Boolean = {
  find(name, table(hash(name))) != null
}
By the bucket-placement representation invariant, an entry with this name can occur only in this bucket. The find contract therefore proves true exactly for keys in the map's domain, with no state change. One hash calculation and one bucket traversal suffice; no insertion is performed during the query.
Assume the supplied hash function is stable and produces valid table indices. The representation invariant places each name in its hashed bucket, permits at most one entry per name, and requires finite acyclic, disjoint bucket chains.
def store(name: String, number: String): Unit = {
  val bucket = hash(name)
  val entry = find(name, table(bucket))
  if (entry == null) {
    table(bucket) = new Entry(name, number, table(bucket))
  } else {
    entry.number = number
  }
}
If the key exists, updating its associated number implements map override without creating a duplicate entry. Otherwise a new entry is prepended to the correct bucket and leaves every existing mapping unchanged. Its immutable name preserves bucket membership. Thus the mapping afterwards is the old mapping overridden at precisely the supplied key. Hash collisions between different names do not imply key equality and are handled by separate chaining.
Use null to indicate that the requested key is absent:
private def find(name: String, head: Entry): Entry = {
  var cursor = head
  while (cursor != null && cursor.name != name) {
    cursor = cursor.next
  }
  cursor
}
The loop invariant is that the skipped string prefix contains no entry with the requested name and cursor starts the unsearched string suffix of the unchanged bucket. Its remaining length is a loop variant. Short-circuit evaluation prevents accessing a null entry. On exit, either cursor is null and the whole bucket has been ruled out, or its name equals the key. No list links or stored numbers are modified. String comparison here uses value equality; node deletion elsewhere uses reference identity.
Let and describe the entry state. The postcondition is: the multiset is empty; the returned chain is sorted nondecreasingly; its node sequence is a permutation of . Thus it has exactly the original multiset of data and preserves all duplicates. Strict increase is impossible when the multiset contains repeated values.
def getAllSorted(): Node = {
  var head: Node = null
  var tail: Node = null
  while (bagHeader.next != null) {
    val nextSmallest = findMin(bagHeader.next)
    delete(nextSmallest)
    nextSmallest.next = null
    if (head == null) head = nextSmallest
    else tail.next = nextSmallest
    tail = nextSmallest
  }
  head
}
The loop invariant partitions the original node identities into the remaining multiset and the returned-prefix chain. The latter is sorted, its last node is tail, and every datum in it is no larger than every remaining datum. Selecting a minimum and appending that detached node preserves all these facts. The loop variant is the number of real nodes remaining in the multiset, decreasing by one. When it reaches zero the string prefix contains the entire original node set, proving the postcondition. An initially empty multiset returns null.
This is linked-list selection sort. Its time is in general, from successive scans of lengths , and it uses constant auxiliary space: it relinks original nodes instead of allocating a new node for each item.
Check that at least one real node exists, then compose the two helpers:
def deleteMin(): Int = {
  require(bagHeader.next != null, "bag is empty")
  val smallest = findMin(bagHeader.next)
  val answer = smallest.datum
  delete(smallest)
  answer
}
The precondition check makes findMin applicable. Its result belongs to the real-node sequence, satisfying delete's precondition. Consequently one minimum value is returned and exactly one occurrence is removed; duplicates remain as distinct nodes. Saving the datum before deletion also separates the return value from subsequent link mutation. Two linear traversals still give time for a multiset containing nodes, with constant auxiliary space.
The precondition is n != null and , using node identity rather than datum equality. Search for its predecessor:
def delete(n: Node): Unit = {
  var previous = bagHeader
  while (previous.next ne n) {
    previous = previous.next
  }
  previous.next = n.next
  n.next = null
}
The loop invariant states that previous is the header or a preceding real node, and . The loop variant is the number of links from previous to n minus one. The precondition guarantees that this search reaches the predecessor before a null dereference. Replacing its successor by n.next bypasses exactly the requested node; clearing the removed node's link detaches it for later reuse. The order and identities of every other node remain unchanged. In abstract terms, only the multiplicity of n.datum decreases, by one. The worst-case time is linear; the pointer modification itself is constant-time.
A sentinel node supplies a permanent predecessor for the first real node. Inserting or deleting at the front then uses the same predecessor.next update as an interior operation. Its datum is not a multiset element: the chosen extreme integer is merely unused sentinel data.
A representation invariant requires a nonnull fixed header, a finite acyclic chain starting at bagHeader.next, and exclusion of the header from that chain. Each node identity occurs once, although different nodes may have equal data. Representation links are owned by the implementation, so outside mutation cannot alter them unexpectedly.
The abstraction function counts occurrences:
This yields nonnegative multiplicities and finite support. Initialization with a null successor gives the empty multiset. Excluding the sentinel is essential even when a real item equals its datum.
For a finite acyclic linked list define the node sequence, retaining software object identities, by
Then scan without changing any links:
def findMin(first: Node): Node = {
  require(first != null)
  var best = first
  var cursor = first.next
  while (cursor != null) {
    if (cursor.datum < best.datum) best = cursor
    cursor = cursor.next
  }
  best
}
At each while loop head, write . The loop invariant says is nonempty, best belongs to , and its datum is no larger than that of every node in . Initially contains only first; comparing the next node extends the processed string prefix and preserves minimality. The loop variant strictly decreases. At exit the whole list is processed, so the returned reference identifies a minimum node. Ties retain the earliest minimum. Time is linear in the number of nodes and auxiliary space is constant.
The implementation maintains the two boundaries from part b:
class ArrayDoubleStack(val MAX: Int) extends DoubleStack {
  require(MAX >= 0)
  private val data = new Array[Int](MAX)
  private var left = 0
  private var right = MAX

  def isEmptya: Boolean = left == 0
  def isEmptyb: Boolean = right == MAX

  def pusha(x: Int): Unit = {
    require(left < right, "double stack is full")
    data(left) = x
    left += 1
  }
  def pushb(x: Int): Unit = {
    require(left < right, "double stack is full")
    right -= 1
    data(right) = x
  }
  def popa: Int = {
    require(left > 0, "stack a is empty")
    left -= 1
    data(left)
  }
  def popb: Int = {
    require(right < MAX, "stack b is empty")
    val answer = data(right)
    right += 1
    answer
  }
}
Initialization gives empty abstract lists. Each push consumes one free position next to the appropriate top; each pop returns that top and releases its position. The guards preserve the ordering of the two boundaries and prevent invalid indexing. The abstraction function shows directly that the untouched stack is unchanged. Keeping data private prevents clients from violating the representation invariant; this strengthens encapsulation relative to a publicly exposed implementation field without changing the six required operations.
All six operations run in time, with a fixed array of MAX integers and constant extra state. Creating and zero-initializing the array takes time, outside those operation bounds. Capacity zero gives a valid always-empty bounded structure whose pushes fail their precondition.
A fixed-capacity implementation needs a bounded contract: , and a push requires strict inequality. Pop preconditions and all successful-operation postconditions remain unchanged. An implementation that rejects full-array pushes cannot satisfy an unbounded specification promising every push; the capacity restriction must be part of the agreed abstract data type, or its resource-failure behavior must be specified.
Use one array and two boundaries left and right. The first stack occupies indices below left and grows rightwards; the second occupies indices at least right and grows leftwards. The representation invariant is
The abstraction function is
Both lists are top-first. The unoccupied middle interval has length right - left; a push is possible exactly when this is positive. Thus every array position can be used by either stack, avoiding a rigid half-array allocation.
Figure 1.
Original shared-array double-stack layout: two stacks grow towards a common free interval
. Details.
Use two finite integer lists , with the head of each list representing its stack top. Initially both are empty. A suitable abstract object interface is
trait DoubleStack {
  def pusha(x: Int): Unit
  def pushb(x: Int): Unit
  def popa: Int
  def popb: Int
  def isEmptya: Boolean
  def isEmptyb: Boolean
}
For the unbounded abstract data type, each push has no logical precondition. The postcondition of pusha(x) is and ; pushb(x) symmetrically gives and . The precondition of popa is , and its postcondition is return value , new state , and unchanged . The specification for popb exchanges . Each emptiness query leaves both lists unchanged and returns exactly whether its corresponding list is empty.
These frame conditions matter: an operation on one stack must preserve the other, not merely produce the right return value.
Sort string suffix starting positions, then examine only adjacent entries:
def longestRepeated(): (Int, Int, Int) = {
  require(N >= 2)
  val suffixes = (0 until N).toArray.sortWith(before)
  var besti = suffixes(0)
  var bestj = suffixes(1)
  var bestk = 0
  var t = 1
  while (t < N) {
    val i = suffixes(t - 1)
    val j = suffixes(t)
    val k = longestFrom(i, j)
    if (k > bestk) {
      besti = i; bestj = j; bestk = k
    }
    t += 1
  }
  (besti, bestj, bestk)
}
The while loop retains a best triple among adjacent pairs already visited. All string suffix starting positions are distinct, and the adjacent-suffix characterization proves that considering these pairs suffices. The two definitions named longestRepeated in parts b and e are alternatives, not duplicate members of one software class.
Assuming a comparison sort using comparator calls, sorting takes time, because each comparison scans characters. The final pass takes . Thus overall time is , at worst , with auxiliary storage for indices and ordinary sorting workspace. Merely storing indices does not make string suffix comparisons constant-time; claiming here would omit their cost. Faster suffix-array constructions require additional machinery beyond this comparator-based solution.
Reuse the verified longest-common-prefix scan, handling equality before scanning:
def before(i: Int, j: Int): Boolean = {
  require(0 <= i && i < N && 0 <= j && j < N)
  if (i == j) false
  else {
    val k = longestFrom(i, j)
    if (j + k == N) false
    else if (i + k == N) true
    else a(i + k) < a(j + k)
  }
}
There is no additional while loop: the helper's loop invariant is that the first k characters agree and both indices remain in bounds. If the second string suffix ends first, the first cannot precede it; if the first ends first, it is a proper string prefix and precedes the second. Otherwise the first mismatching characters decide lexicographic order. Distinct suffixes cannot both end after the same number of characters, since their lengths differ.
The i == j case ensures a strict comparator, returning false for a string suffix compared with itself, in constant time. For distinct suffixes its running time is , where is the longest repeated-substring length of the full array.
All suffixes beginning with a fixed string form an interval in lexicographic order. To see this, suppose two suffixes start with a string , while a string suffix between them fails to start with . At its first differing character it must be either smaller than both or larger than both; if it ends before does, it is smaller than both. Either possibility contradicts its position between them.
Now take a longest repeated substring . Its two occurrences are prefixes of two distinct suffixes. Every string suffix between them also begins with , so at least one adjacent pair in that interval has a common string prefix of length at least . A greater length would contradict maximality of . Therefore the maximum common-prefix length over adjacent sorted suffixes equals the longest repeated-substring length. If the maximum is zero, any adjacent pair still attains it. The argument does not assume nonoverlapping occurrences.
Figure 1.
Original suffix-array example for banana: an interval of suffixes shares the repeated prefix ana
. Details.
Compare every unordered pair of distinct starting positions:
def longestRepeated(): (Int, Int, Int) = {
  require(N >= 2)
  var besti = 0
  var bestj = 1
  var bestk = 0
  var i = 0
  while (i < N - 1) {
    var j = i + 1
    while (j < N) {
      val k = longestFrom(i, j)
      if (k > bestk) {
        besti = i; bestj = j; bestk = k
      }
      j += 1
    }
    i += 1
  }
  (besti, bestj, bestk)
}
After each comparison, the stored triple attains the largest common-prefix length among pairs processed so far; its positions remain distinct. The nested while loops enumerate exactly pairs. Reversing the two positions does not change their common-prefix length, so no omitted ordered pair could improve the answer. Initialization also supplies a valid length-zero answer if no character repeats.
Write for the final maximal length. Each comparison takes time, including a possible first mismatch. Hence time is , at worst , and auxiliary space is . Writing merely would miss the case. The explicit precondition excludes arrays with fewer than two valid starting positions; the requested distinct-position triple has no answer there under this domain convention.
Scan the two suffixes until a mismatch or an endpoint:
def longestFrom(i: Int, j: Int): Int = {
  require(0 <= i && i <= N && 0 <= j && j <= N)
  var k = 0
  while (k < N - i && k < N - j && a(i + k) == a(j + k)) {
    k += 1
  }
  k
}
The loop invariant is and equality of the two array segments of length . The loop variant is , which decreases whenever the while loop runs. Short-circuit evaluation checks both bounds before indexing. On exit either a string suffix has ended or the next characters differ, so no longer common string prefix is possible. Thus the returned value is the longest common prefix length. Overlap is allowed: the code only reads the array, so the two matching segments need not occupy disjoint storage.
First find a sign bracket by exponential search, then bisect that bracket without evaluating its endpoints again:
def floorRoot(): Int = {
  require(eval(0.0) < 0.0)
  var lo = 0
  var hi = 1
  while (eval(hi.toDouble) <= 0.0) {
    lo = hi
    require(hi <= Int.MaxValue / 2, "doubling bound exceeds Int range")
    hi *= 2
  }
  while (hi - lo > 1) {
    val mid = lo + (hi - lo) / 2
    if (eval(mid.toDouble) <= 0.0) lo = mid
    else hi = mid
  }
  lo
}
For the first while loop the loop invariant is , with hi a positive power of two, and either or . Every previously tested power of two has nonpositive value. Let be the least nonnegative integer for which . It exists by the positive leading coefficient. If the current upper endpoint is , a mathematical loop variant is while the guard holds; the next doubling decreases it by one. The first while loop's postcondition is . The second while loop has exactly the invariant, variant and adjacent-integer postcondition established in part c.
There are evaluations at powers of two. If , the final bracket has width and takes exactly midpoint evaluations. Including the initial sign check, the total is evaluations for , and two for . Thus evaluation cost is for the first positive dyadic bound ; it is not a claim about the first positive root of a polynomial when the polynomial is nonmonotone.
The mathematical argument uses unbounded integer endpoints and reliable signs. The guarded Int implementation requires the successful dyadic bound to fit in Int; otherwise it explicitly fails rather than wrapping to a negative bound. The coefficient assumptions alone cannot guarantee that a requested integer result fits a fixed-width type. Floating-point overflow or unreliable signs likewise need a wider or certified evaluator for a fully general implementation.
Maintain opposite signs at the endpoints, rather than assuming that the polynomial is monotone:
def floorRoot(X: Int): Int = {
  require(X > 0 && eval(0.0) <= 0.0 && eval(X.toDouble) > 0.0)
  var lo = 0
  var hi = X
  while (hi - lo > 1) {
    val mid = lo + (hi - lo) / 2
    if (eval(mid.toDouble) <= 0.0) lo = mid
    else hi = mid
  }
  lo
}
The loop invariant is and . Both branches preserve those signs, even when there are other roots of a polynomial or sign reversals elsewhere. When the interval width exceeds one, the midpoint is strictly between its endpoints, so the positive integer loop variant hi - lo strictly decreases. On exit hi == lo + 1, giving the required postcondition . Continuity establishes a root of a polynomial between those adjacent integers, possibly at the left endpoint.
The width is at most halved with rounding upwards, so there are at most midpoint evaluations, plus two endpoint evaluations in the precondition check. The midpoint expression avoids adding two large endpoints. The explicit positive upper-bound precondition supplies the interval order assumed in the question. For the literal computed-eval contract, the same proof holds provided evaluated midpoints are not NaN; identifying its bracket with the real polynomial additionally requires trustworthy evaluation signs.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact