The loop invariant just before inspecting index $i$ is: $0\le i\le n$, and no entry at an index $k<i$ matches $x$. Initially $i=0$, so there are no earlier entries. A failed equality test extends the excluded region by one position and preserves the loop invariant. A successful equality test at index $i$ establishes a match; the loop invariant establishes that it is the first one. At exhaustion, $i=n$ and every entry has failed, so the absent result is correct. The number $n-i$ of remaining entries decreases after each failed equality test, proving termination for a finite sequence. Together these establish algorithm correctness under the assumptions that the input is stable and each equality test terminates. No step of the argument compares the relative order of values.

Count just the equality tests between the target and an entry, excluding loop conditions and index updates. If the first match is at index $j$, linear search uses exactly $C=j+1$ equality tests. If the target is absent, it uses exactly $C=n$. Thus for $n\ge 1$ the best successful case costs one equality test, and the worst case costs $n$, attained by absence or a first match at the last index. For $n=0$, the sole outcome is absence with $C=0$.

An expected value needs a specified probability distribution. For $n\ge 1$, condition on success, assume the target occurs exactly once, and assume its position $J$ has a uniform distribution on a finite set of indices $0,\dots ,n-1$. Then the expected value of the linear search comparison count isThis is the average of the costs $1,2,\dots ,n$ under those assumptions, with no assumption that the array is sorted. It is not a universal average for arbitrary queries. For example, with $n=5$, a unique successful target at index $0$ with probability $3/4$ and at index $4$ with probability $1/4$ has expected value $(3/4)\cdot 1+(1/4)\cdot 5=2$, rather than $3$.

Duplicates also require care about what is sampled. Choose a position uniformly in $[7,4,7,2,9]$, then search for its value. All queries succeed, but the five possible sampled positions give costs $1,2,1,4,5$: both positions holding $7$ cause an immediate match at index $0$. The expected value is $13/5$, not $(5+1)/2$. Uniformly choosing an occurrence does not uniformly locate the first match.

More generally, let the success probability be $p>0$ and let $q_j$ be the conditional probability that the first matching index is $j$, allowing duplicates. Since ${\sum }_{j=0}^{n-1}{q}_j=1$, the expected value isUnder the unique, uniformly located successful-target assumptions this becomes $p(n+1)/2+(1-p)n$. If every query is absent, $p=0$ and $C=n$ without needing conditional probabilities. When $n=0$, success is impossible and $C=0$; the successful-search conditional formula is undefined.

Converting the linear search comparison count to execution time needs a cost model. Under constant-cost equality tests, next-entry access, and loop bookkeeping, worst-case time complexity is $O(n)$ in Big O notation for $n\ge 1$, with constant overhead even for the empty sequence. Variable-length entries can make an equality test expensive. On a linked list, advance along its links; repeatedly restarting at the head to obtain the next numeric index adds work that the comparison count does not capture. These are exact operation counts and conditional mathematical averages, not runtime measurements.

A low-pass filter preferentially transmits low frequencies and attenuates higher frequencies. It can smooth rapid noise in a slowly varying signal, but it also suppresses wanted variations outside the useful signal bandwidth. An RC low-pass filter gives a concrete continuous-time example; a moving average implements related smoothing on a discrete-time signal.

The useful question is how much change the measurement can tolerate. Preserving the low frequencies of a temperature record while reducing a fast unwanted oscillation can improve readability. Preserving the sharp onset of a pulse requires higher frequencies, so excessive smoothing changes its timing and shape. The RC low-pass frequency response and RC low-pass step response make this signal bandwidth versus settling time tradeoff quantitative.

Issued by National Council of Educational Research and Training.

Online text: www.ncert.nic.in/pdf/publication/sciencelaboratorymanuals/classXII/physics/lelm306.pdf

Cited passages: Experiment 6, printed pp. 53–58: Figure E 6.1, Procedure 1–5, Precautions and Sources of Errors; Experiment 6, printed pp. 54–55, equations (E 6.2), (E 6.8) and (E 6.9); p. 58, Self Assessment 4.

Online text: goldbook.iupac.org/terms/view/15225

Gold Book entry 15225, in the fifth-edition online version 5.0.0 (2025), issued by IUPAC. The entry cites 2009 recommendations, p. 994; no individual editors or recommendation authors are inferred here.

Cited passages: IUPAC Compendium of Chemical Terminology, fifth edition, entry “polymorph” (15225), definition and Note 2.

Online text: goldbook.iupac.org/terms/view/M03988

Cited passages: Gold Book, fifth edition, molecular ion in mass spectrometry: formation by electron removal or addition without fragmentation.

Online text: goldbook.iupac.org/terms/view/M04002

Cited passages: Gold Book, fifth edition, molecule: neutral entity with more than one atom; bound-state qualification.

Online text: goldbook.iupac.org/terms/view/O04344

Cited passages: Gold Book, osmotic pressure: definition of the solvent-only membrane; Gold Book, osmotic pressure: equilibrium definition, solvent activity formula and dilute ideal limit.

Online text: sites.math.washington.edu/~lee/Books/ITM/c01.pdf

Author-hosted sample of Chapter 1, Introduction. The second-edition book is credited to John M. Lee, published by Springer in Graduate Texts in Mathematics 202, and carries copyright 2011. Its Chapter 1 definition is explicitly provisional; formal manifold hypotheses in this wiki are supported by the separately cited Toronto notes.

Cited passages: Introduction to Topological Manifolds by John M. Lee, second edition, Chapter 1, pages 1–3 on local models and pages 5–6 on topological invariants.

Online text: introcs.cs.princeton.edu/java/44st/

Cited passages: Introduction to Programming in Java, section 4.4, Binary search trees: recursive definition and node representation.

By Daniel Dadush.

Online text: homepages.cwi.nl/~dadush/teaching/lattices-2018/notes/lecture-1.pdf

Lecture 1 notes credit Daniel Dadush as scribe, with Daniel Dadush and Léo Ducas listed as lecturers. Mastermath Spring 2018 identifies the course offering; no publication year or whole-course authorship is inferred.

Cited passages: §7, Definition 11 and Lemma 12, printed p. 9: determinant and integer-inverse characterization; §7, Lemma 13, printed p. 9: equivalent lattice bases.

Use the compilation arithmetic example with input $x=7$. An abstract syntax tree interpreter first reads x, obtains $2+3=5$, forms $7\cdot 5=35$, and finally computes $35-4=31$. Interpreting the folded abstract syntax tree skips the addition but gives the same result. The compiled stack machine instructions instead produce the following trace; the top of the stack is written on the right:

instruction    stack after instruction
initial        []
LOAD x         [7]
PUSH 5         [7, 5]
MUL            [35]
PUSH 4         [35, 4]
SUB            [31]

The order in SUB is essential: reversing its two popped operands would give $4-35=-31$. The same stored instruction sequence works for input $x=-2$, yielding $(-2)\cdot 5-4=-14$, without repeating parsing or constant folding. An abstract syntax tree interpreter can likewise reuse its already-parsed tree. Reusing a representation is therefore useful to both approaches; it does not itself distinguish compilation from interpretation.

The pleasing part is that a nested rooted tree and a flat instruction sequence express the same computation. The structural induction in the compilation arithmetic example connects them by a precise stack property. This tiny language always terminates and has no side effects; richer programming language semantics require a correctness argument that also accounts for failures, externally visible actions, and possible nontermination.