Here are fixed integers. The term has exponential growth, whereas has fixed-degree polynomial growth and is linear. Since a fixed-base exponential eventually dominates every fixed-degree polynomial,Hence the requested Big O notation bound, with its matching lower order, is .
The printed fractional arguments require a size convention. To make the recurrence relation precise on positive integers, take a bounded base case and use , for . This integer rounding in a divide-and-conquer recurrence gives . The unrounded calculation is the special split fraction .
Prove by strong induction. Put , choose , and choose . The base case follows. The entropy potential for a divide-and-conquer recurrence givesThe last step uses . This closes the inductive hypothesis and proves in Big O notation.
The solutions use the original 17 June 2014 preliminary examination, code
4208.[ref]Functional programming, design and analysis of algorithms examination paper by the University of Oxford (2014). original scan, pp. 2–8
Haskell definitions use separate question namespaces; names suffixed F or U distinguish alternative implementations. For Question 4, use import Prelude hiding (foldr, (++), concat, flip) when compiling the definitions together. Unless an infinite input is discussed explicitly, inputs are finite and total. Arithmetic operation counts do not include the growing bit costs of exact integers.[ref]The two constructors encode a natural number by its number of successors. Structural recursion replaces the zero constructor by zero and every successor by one addition:
convert :: Natural -> Integer
convert Zero = 0
convert (Succ n) = 1 + convert nStructural induction gives . The output uses unbounded integers, so there is no machine-word overflow.
The scan permits an arbitrary signed integer but prints . That expression is undefined for . The printed bound is proved below for positive ; for the stated signed domain the corresponding bound uses . This is a source qualification, rather than an unreadable part of the question.[ref]
Functional programming, design and analysis of algorithms examination paper by the University of Oxford (2014). p. 7, Question 5(b), printed logarithm and final absolute-value sentence
Choose a fixed positive integer with , and put . For positive , use coarse exponential bracketing: compare against until the first . Equality determines immediately. Otherwise, , except in the first interval where the lower bound is zero. Apply binary search to the remaining integer candidates.
There are at most bracketing comparisons and at most subsequent comparisons, because the interval width is at most . Minimality of gives . HenceThe additive constant may depend on the fixed , but is independent of . Taking larger jumps in the bracketing phase reduces its leading comparison cost; the overshoot costs only the fixed number of extra binary search levels.
For signed inputs, first compare with zero. If negative, set conceptually and perform the same search for : comparing with yields the reversed outcome of comparing with . Thus every test is still a permitted test of the sign of . Return zero immediately on equality in the initial test. The corrected all-input bound isAll thresholds are exact integers, generated by repeated multiplication by . Their arithmetic and storage costs are outside the requested comparison model; bounded machine arithmetic would not suffice for arbitrarily large .
Assume . Use bottom-up heap construction to make a max-heap of the first input items. For each subsequent input value , compare it with the root. If is at least the root, discard it; otherwise replace the root by and apply heapify down. Return the final root.
The loop invariant says the heap contains a multiset of the smallest values seen so far. It holds after initialization. If is at least the current largest retained value, the already retained items are no larger, so discarding preserves the invariant. If is smaller, remove one largest retained value and keep instead; precisely the smallest values remain. This argument handles equal integers by treating repeated occurrences as separate items. At the end,Construction costs ; each remaining value uses one comparison and at most one logarithmic repair. Thus the selection algorithm has time complexityFor , the heap is a single running minimum and the time is . The uniform expression covers that boundary; interpreting the printed literally at would incorrectly make it zero.
Take an integer pivot . There are possible values in but only occurrences of such values in the whole array. When , the pigeonhole principle givesRepeated values do not invalidate the argument: they can only reduce the number of distinct values represented by those occurrences. The other side might also contain a missing value.
Use missing-value search by deficient value intervals: halve the candidate value interval, and apply array partitioning only to the array segment whose entries lie in that interval.The loop invariant is , , andMore precisely, the segment contains all occurrences of original values in , and the complete array remains a permutation of its original state. The occurrences statement is essential: absence from the final segment must imply absence from the original array.
def missing(): Int = {
require(N < Int.MaxValue)
var lo = 0; var hi = N + 1
var l = 0; var r = N
while (hi - lo > 1) {
val p = lo + (hi - lo) / 2
val k = partition(l, r, p)
if (k - l < p - lo) {
hi = p; r = k
} else {
lo = p; l = k
}
}
lo
}After array partitioning, let , , , and . If , retain the left side. Otherwise the right side hasoccurrences. Either choice preserves the strict deficiency and the all-occurrences condition. The positive integer width decreases, proving termination. At width one, the active segment has fewer than one entry and is empty. ThereforeFor the time complexity, after splits the width is at most , and the scan length is smaller than that width. Summing over the levels gives a geometric series plus logarithmic overhead, hence overall, conventionally for . This proof bounds the retained occurrence count by the retained value width; it does not assume that each array partitioning splits the number of occurrences in half. The case returns zero immediately.
Use the iterator adapter from part (b) with a primality test by trial division. A composite positive integer has a divisor no greater than its square root.Before each trial division iteration, no integer in divides
def primeIter(upperBound: Int): Iter[Int] = {
def isPrime(n: Int): Boolean = {
if (n < 2) false
else {
var d = 2
while (d <= n / d && n % d != 0) d += 1
d > n / d
}
}
filterIter[Int](isPrime _, new RangeIter(2, upperBound, 1))
}n. If division succeeds, the condition becomes false with , and isPrime returns false. Otherwise the loop ends with , so every possible small divisor has been excluded. The quotient comparison is equivalent to for positive values and avoids integer overflow in d*d.Bounds at most two give an empty iterator. This method tests candidates lazily and uses trial divisions for candidate ; no efficiency requirement in the question forces a sieve of Eratosthenes implementation.A computed memory address is just another integer on the operand stack. For a pointer held at fixed address ,
const p; load obtains the pointed-to address; another load obtains its contents. More generally, any expression that leaves an address on top may be followed by load, or may be retained beneath a computed value for store.For an array whose base address is and whose element size is address units, the address of entry is , where stores the index. Add zero-address instructions The first six instructions leave the element address . The remaining suffix evolves aswith the final effectThe address is computed once and duplicated, so both accesses refer to the same array element. For unit-sized elements omit
mul and dup, with dup mapping to . A suitable sequence isconst b
const p_i
load
const w
mul
add
dup
load
const 1
add
storeconst w; mul. If the base address is itself held in a variable, replace const b by the instructions loading that variable's value. No instruction other than const requires an explicit operand.Let and measure the extra operand stack space required from the current base, with each evaluation leaving one result. Evaluating first uses slots. Its result occupies one slot while evaluating , so that stage uses slots. The final
add reduces two slots to one. ThusBy commutativity of addition, choose the smaller of these two bounds. Evaluate the child of larger depth first. The optimum recurrence on a binary expression tree isAssign depth one to a literal or a simple already-addressable value, and compute the child depths recursively. If , the depths are integers, so ; evaluating first therefore attains , while reversing the order needs . If the depths are equal, whichever child goes second needs the extra retained-result slot. These lower bounds prove the recurrence is optimal for evaluating each child subtree without interleaving or spilling. Apply it at every node to minimize peak operand stack occupancy for the given binary expression tree; this is optimal stack evaluation of a binary expression tree.This changes child evaluation order, not the parenthesization. For example, a chain-shaped binary expression tree can have depth two, whereas a balanced tree of eight leaves has depth four under this model. The reordering assumes expressions have no order-sensitive side effects or observable exceptions. Reassociating floating-point addition would require additional care because it can change floating-point rounding.
A file descriptor table belongs to a process: its small nonnegative integer indices are file descriptors, and each occupied entry points to an open file description. It also holds descriptor-specific information, such as whether the descriptor closes on a successful program replacement. There is one logical file descriptor table per process in the traditional model; implementations can let processes explicitly share one.
The system-wide open file table, called the file pointer table here, contains open file descriptions. Each entry records an opening's access mode, current file offset, reference count and reference to an in-memory inode. Duplicated file descriptors, including inherited ones, can refer to the same open file description and therefore share its file offset. Independent opens of the same file normally create separate open file descriptions and separate offsets. There is one logical system-wide open file table, with many entries.
The system-wide in-memory inode table caches the inodes currently needed, including shared file metadata, locking and reference information. Its identity key must include the file system as well as the inode number when several volumes are mounted. There is one logical system-wide active inode table, distinct from the persistent inode table stored on each volume. These are logical organizations, not requirements for a single contiguous array in memory.
Suppose the definition of big O notation held with constants . Choose an odd integer . At this input, and , so the required inequality would be , a contradiction. ThusThe infinitely many even inputs, where , cannot repair the failure on odd inputs because the bound must hold for every sufficiently large input.
The Euclidean division gives with and . Writing givesSince is an integer, this proves the divisibilityincluding .
The greatest common divisor is the largest positive integer dividing both inputs:This maximum exists because belongs to the set and all its elements are at most .
Count the final division producing zero as an iteration, and let the total be . The terminal product alone gives no useful bound. Instead apply (i) to each nonterminal product, which is a positive integer and hence at least .
If , the penultimate product satisfiesAs is an integer, this impliesFor , the same bound holds since implies . In particular the Euclidean algorithm uses divisions, in big O notation. The convention that includes the final zero-producing division explains the one-step offset in the argument.
Using the probability mass function of the Poisson distribution directly givesFor each fixed positive integer , this series converges: the ratio of successive nonzero terms is , which tends to zero. Equivalently, using the polynomial identity in (ii) and the factorial moments from (a)(iv) gives ; the extension of that identity to is justified in (iv).
Both sides of (ii) are polynomials in the colour count, and they agree at every integer . A nonzero polynomial has only finitely many roots, so this is a polynomial identity and holds also at . It can therefore be evaluated at every possible value of the Poisson random variable .
Take expectations and use the factorial moments from (a)(iv). The sum over is finite, so linearity of expectation givesCombining this with (iii) proves Dobiński's formula for the Bell numbers:For completeness, the empty set has one partition of a set, giving ; that case uses the empty-product conventions in this identity and a term in the partition sum.