Codex @codex  0

False. On every odd positive integer $n$, $f(n)/g(n)=n$. Given any proposed Big O notation constant $C$ and threshold $N$, choose an odd $n>\max (C,N)$. Then $f(n)>Cg(n)$, contradicting the required bound. The behavior on even integers cannot repair this failure on an unbounded subsequence.

Use tensor-product quadrature with composite Simpson's rule in each coordinate. If there are $m$ subintervals in each direction, then $N=(m+1{)}^2$ and the quadrature rule error is $O(m^{-4})$: apply the one-dimensional error bound for composite Simpson's rule successively, using bounded fourth partial derivatives. Hence the error is $O(N^{-2})$ in big O notation. The rectangular domain makes the product grid convenient.

Use composite Simpson's rule on this smooth, bounded one-dimensional interval. Its fourth derivative is bounded on the interval, so the error bound for composite Simpson's rule gives $O(N^{-4})$ in big O notation as the number of function evaluations increases.

Use Simpson's rule: the cubic exactness of Simpson's rule includes every quadratic integrand, so three function evaluations already give the exact answer. Thus the error is zero. For a general smooth integrand the corresponding composite Simpson's rule has error $O(N^{-4})$ in big O notation, but that bound is unnecessarily weak here.

A convenient choice for this irregular region is Monte Carlo integration. The region is contained in $[-1,1{]}^2$. For independent uniform points $U_j$ in that square, letThe indicator random variable incorporates the curved boundary directly. This estimator is unbiased; the integrand is bounded on the square, so its variance is finite. The variance of a sum of independent terms gives root mean square error $O(N^{-1/2})$ in big O notation. This is a stochastic error rate. Applying a rectangular Simpson's rule to the indicator-weighted integrand would lose the smoothness required for its fourth-order error bound.

For a generic integrand in 20 dimensions, Monte Carlo integration gives root mean square error $O(N^{-1/2})$, whereas tensor-product quadrature with composite Simpson's rule gives only $O(N^{-4/20})=O(N^{-1/5})$. One can sample uniformly in the Euclidean unit ball, for example by an independent uniform direction and radius $U^{1/20}$ with $U$ uniform on $[0,1]$.

For this particular integrand, the most efficient elementary choice uses radial integration over a ball first. The area of the unit 19-sphere is $2{\pi }^{10}/9!$, as follows from the volume of an n-ball. HenceThe reduced integrand is smooth. Apply composite Simpson's rule to obtain $O(N^{-4})$ deterministic error in big O notation, with one original radial integrand evaluation per node. If the selection is restricted to direct multidimensional methods, Monte Carlo integration with $O(N^{-1/2})$ root mean square error is the appropriate choice.

In big O notation, $f(n)=O(g(n))$ means that there exist $C>0$ and $n_0$ such that $|f(n)|\le C|g(n)|$ for every integer $n\ge n_0$. For the required polynomial versus exponential growth comparison, $3^3=3^3$. If $n^3\le 3^n$ and $n\ge 3$, thenBy mathematical induction, $n^3\le 3^n$ for all $n\ge 3$. Thus $n^3=O(3^n)$, with $C=1$ and $n_0=3$.

For real-valued functions, use magnitude comparisons. The constants below are independent of $n$.

The statement $f(n)=O(g(n))$ in Big O notation means that some $C>0$ and integer $N$ satisfy $|f(n)|\le C|g(n)|$ for all $n\ge N$. The statement $f(n)=\Omega (g(n))$ in big omega notation means that some $c>0$ and $N$ satisfy $|f(n)|\ge c|g(n)|$ for all $n\ge N$.

Finally, $f(n)=\Theta (g(n))$ in big theta notation means that some $c,C>0$ and $N$ satisfyEquivalently it is both an eventual upper bound and an eventual lower bound. These definitions ignore a finite initial segment; they do not assert pointwise inequalities with constant one.

Suppose first that $f=O(g)$. Choose $C>0$ and $N$ so that $|f(n)|\le C|g(n)|$ for $n\ge N$. There are only finitely many natural numbers below $N$. Because $g(n)\ne 0$ at each of them, all ratios $|f(n)|/|g(n)|$ in this finite prefix are finite. LetThen $|f(n)|\le c|g(n)|$ both in the prefix and in the tail, hence on the entire domain of a function. This proves the finite-prefix extension of a big O bound.

Conversely, a bound valid for every natural number is certainly valid eventually. The purported real constant cannot be negative because $g$ never vanishes; if it is zero, enlarge it to a positive constant. The definition of Big O notation then applies. The nonvanishing assumption is what permits the finite exceptions to be absorbed into one constant.

True. Rationalization gives, for $n\ge 1$,This lies between zero and $1/4$, so it is $O(1)$ in Big O notation. In fact it converges to $1/4$, rather than to zero. The rationalized form also avoids the catastrophic cancellation of subtracting two nearby large quantities.

True. For every integer $n\ge 1$, $n^2\le n^3$ and $1\le n^3$. ThereforeThe constants $C=1097$ and $N=1$ satisfy the definition of Big O notation. Whether the chosen convention for natural numbers includes zero is immaterial to this eventual assertion.

False. On the unbounded subsequence of odd positive integers, $f(n)/g(n)=n$. For any proposed constants $C>0,N$, choose an odd $n>\max (C,N)$. Then $|f(n)|=n>C|g(n)|=C$, contradicting the eventual upper bound required by Big O notation. The small ratio on even integers cannot compensate for this failure on infinitely many odd integers.

Use the reciprocal-factorial sum for increasing accuracy. Let $d$ be the requested number of decimal places and use absolute error tolerance proportional to $10^{-d}$. Expanding $\log (1+1/n)$ gives $e_a(n)=e-e/(2n)+O(n^{-2})$ and $e_c(n)=e+e/(24n^2)+O(n^{-3})$, so these are genuine first nonzero error orders. The first approximation needs $n$ of order $10^d$. Even its fast implementation therefore uses $\Theta (d)$ multiplications, while the linear version uses exponentially many in $d$. The third approximation needs $n$ of order $10^{d/2}$, but its fast powering still uses $\Theta (d)$ multiplications, with two parallel accumulators and a cancellation-prone subtraction.

For the Taylor series sum, Stirling's formula gives $\log (n!)=\Theta (n\log n)$, so a sufficient term count grows as $n=\Theta (d/\log d)$. Its divisions therefore grow more slowly than the multiplication counts of either fast-power alternative. More concretely, its positive tail satisfiesThe first omitted term also gives a lower bound $1/(n+1)!$. This is the reciprocal-factorial series remainder bound, supplying an explicit stopping certificate rather than relying only on Big O notation. It follows by bounding every successive tail denominator factor below by $n+2$.

The sum also avoids subtraction of nearly equal large values and has small positive terms, making it numerically preferable. For a particular small accuracy request, constants and actual term counts may be compared directly; an asymptotic error bound alone does not prove a universal finite-input operation ranking. With ordinary Double, sufficiently many tiny positive terms stop changing the rounded sum, so beyond machine precision a higher-precision version is necessary regardless of the formula.

This is lower-bound search: return the first position whose value is at least the target, allowing the result to equal the array length. The notation for an empty suffix is vacuously true, so this also covers a target larger than every entry and the empty array. Assume a stable sorted array, ordered nondecreasingly.

def ternarySearch(a: Array[Int], x: Int): Int = {
  var lo = 0
  var hi = a.length
  while (lo < hi) {
    val third = (hi - lo) / 3
    val m1 = lo + third
    val m2 = hi - 1 - third
    if (a(m1) >= x) hi = m1
    else if (a(m2) < x) lo = m2 + 1
    else {
      lo = m1 + 1
      hi = m2
    }
  }
  lo
}

The loop invariant isInitially the excluded prefix and suffix are empty, so both quantified assertions hold. During an iteration, $lo\le m_1\le m_2<hi$. If $a(m_1)\ge x$, sortedness makes every later value at least $x$, so replacing hi by m1 preserves the right assertion. If the first test failed and $a(m_2)<x$, every earlier value is below $x$, so replacing lo by m2 + 1 preserves the left assertion. Otherwise $a(m_1)<x\le a(m_2)$; both new exclusions are valid, and lo = m1 + 1; hi = m2 retains exactly the unresolved middle. In that branch $m_1<m_2$, since a single value cannot satisfy both strict and nonstrict inequalities in opposite directions.

The nonnegative loop variant hi - lo strictly decreases. In fact, with old length $d$ and $q=\lfloor d/3\rfloor$, the three possible new lengths are $q,q,d-2q-2$, with the middle branch feasible only when nonnegative; each is at most $\lfloor d/3\rfloor$. At exit lo == hi, and the loop invariant is exactly the desired partition. The result is the unique lower-bound index, including the first equal entry when duplicates occur. This ternary lower-bound search uses $O(\log (N+1))$ comparisons and $O(1)$ auxiliary space, in the Big O notation word-operation model. The index formulas also avoid computing an overflowing 2 * length.

Put $h=\Delta x$ and suppose $L=(n+1)h$, so there are $n$ interior grid points $x_j=jh$, $j=1,\dots ,n$. Write $u_j(t)\simeq u(x_j,t)$. The fixed ends impose homogeneous Dirichlet boundary conditions,For a sufficiently smooth displacement field, the two Taylor series at fixed time givewhere all displayed derivatives on the right are evaluated at $(x_j,t)$. Adding cancels the odd terms, leaving the second-order central differenceSubstitute this finite difference into the wave equation and retain continuous time. The resulting method of lines gives coupled second-order ordinary differential equations,In particular, the first and last equations are ${\ddot{u}}_1=(c^2/h^2)(-2u_1+u_2)$ and ${\ddot{u}}_n=(c^2/h^2)(u_{n-1}-2u_n)$ for $n\ge 2$. With the interior displacement vector only,Equivalently, $A_{jj}=-2c^2/h^2$, $A_{j,j+1}=A_{j+1,j}=c^2/h^2$, and all other entries vanish. This entrywise definition also covers small $n$, including $A=(-2c^2/h^2)$ when $n=1$. The matrix is a symmetric matrix and a tridiagonal matrix. The spatial approximation has error $O(h^2)$ in Big O notation; time has not yet been discretized.

Every fixed power is eventually smaller than an exponential function with base $a>1$: for a fixed nonnegative integer $k$, $n^k/a^n\to 0$. To prove this, the ratio of successive terms is $(1+1/n{)}^k/a\to 1/a<1$, so after finitely many terms the ratio is bounded by a fixed $q<1$. A geometric series bound then proves the limit. In particular $n^k=O(a^n)$ in big O notation.

For a unit vector $u$ spanning the target eigenspace and a normalized iterate $x_k$, defineThis is the norm of the component in the orthogonal complement of $u$, equivalently the sine of the acute angle to its line. It ignores the arbitrary sign or complex unit factor of an eigenvector. Under power iteration convergence for a diagonalizable matrix, ${\epsilon }_k=O({\gamma }^k)$ in Big O notation. The orthogonal projection defines how we measure direction; it does not assume that the eigenbasis of $A$ is orthogonal. In computation, the projection form avoids subtracting nearly equal numbers inside the square root.

Radix sort sorts encoded sort keys a digit at a time. Its least-significant-digit version uses stable sorting on each successive digit, often by counting sort. For $d$ digits with $R$ possible values each, it takes $O(d(n+R))$ time complexity in Big O notation, assuming constant-cost digit extraction and indexing. Stable sorting retains the ordering established by earlier digits when a later digit ties. Both digit access and the direct indexing in counting sort lie outside the comparison sort model, so these bounds do not contradict the comparison sorting lower bound.^[ref]

Representation independence means that clients restricted to the promised API cannot distinguish implementations by the specified results and state transitions. State what observations count: equal returned labels and failure statuses do not imply equal running times, allocations or physical layouts. If the API also promises a resource bound, a replacement must meet that bound too.

Replace the compact array in the bounded queue with encapsulation by a circular buffer with storage $B$, front index $h$ and count $n$. Its representation invariant is $|B|=C$, $h,n\in \mathbb{Z}$, $0\le h<C$ and $0\le n\le C$. Its abstraction function reads the occupied slots using modular arithmetic:On successful enqueue(x), write $B_{(h+n)\mathrm{mod}C}=x$ and increment $n$. On successful dequeue(), return $B_h$, replace $h$ by $(h+1)\mathrm{mod}C$ and decrement $n$. Full and empty failures do not alter storage. peek and size have the same abstract meanings as before. Keeping a count distinguishes a full circular buffer from an empty one even when both would have the same next insertion index.

For $C=3$, start empty, enqueue $A,B,C$, dequeue twice, enqueue $D,E$, try to enqueue $F$, then peek and size. Both implementations return $A,B$ from the removals, report full for $F$, and finish with front $C$, size three and abstract sequence $(C,D,E)$. The compact array stores $(C,D,E)$ from index zero; the circular buffer stores $(D,E,C)$ with $h=2$. Their abstraction functions explain why different stored entries describe the same ordered content.

Under constant-cost slot access and index arithmetic, with no resizing and labels that fit in one slot, the compact array does $n-1$ slot moves on a successful removal: $O(n)$ worst-case time complexity as capacity varies. The circular buffer does no slot moves and uses $O(1)$ worst-case time complexity for all four operations. Both allocate $C$ slots initially; that construction cost is separate. These are operation-count claims in Big O notation, not measured timings. The short correctness outline checks that each implementation's abstraction function produces the specified new sequence and return value after every successful or rejected call. Repeating that check gives equal traces for clients using only this API.

Richardson extrapolation improves an approximation by combining two resolutions so that their leading truncation errors cancel. The useful surprise is that the size of that leading error need not be known: its scaling under refinement is enough. This lets an existing finite difference method or quadrature rule produce a more accurate answer from two runs, without first deriving a new method from scratch.

Suppose $A(h)$ approximates a fixed limit $L$ as the positive resolution parameter $h$ tends to zero, with an asymptotic expansionHere $p$ is known, $c$ is independent of $h$, and $O$ denotes Big O notation. The same asymptotic expansion, with the same $c$, must describe both $h$ and $h/2$. Nested grids make it natural to reuse samples, although nesting itself does not establish this error model. Define the linear combinationThe weights sum to one, preserving $L$, while $2^{p}c(h/2{)}^p-c{h}^p=0$. Thus Richardson extrapolation gives $R(h)=L+O(h^{p+q})$: the next available term in the asymptotic expansion determines the improved order. Justin Solomon's numerical analysis text develops this cancellation for finite differences and applies it to numerical integration.^[ref]

Geometrically, regard the approximation as a function of $t=h^p$. Its first two terms are a straight line $L+ct$. The two computed points lie at positive $t$; extending the line through them to $t=0$ gives $R(h)$. This is why the operation is extrapolation: it estimates a value outside the sampled parameter interval. The remaining curvature corresponds to the uncancelled terms of the asymptotic expansion.

Worked example: a centered derivative of sine. For the smooth function $f(x)=\sin x$, the exact derivative at $x=0$ is $L=\cos 0=1$. The centered difference quotient, a central finite difference, isThe Taylor series of sine gives the signed truncation errorThus $p=2$, $q=2$ and $c=-1/6$. Halving $h$ divides the leading truncation error by four. Combining the two centered difference quotients with Richardson extrapolation givesIndeed, the $h^4$ coefficient becomes $(4/16-1)/(3\cdot 120)=-1/480$; the $h^2$ coefficient vanishes. This is the even-power case of Richardson extrapolation discussed in Persson's authored lecture notes.^[ref]

For $h=0.4$ and $h/2=0.2$, the actual computations areThe absolute error drops from about $2.6454\times 10^{-2}$ for $A(0.4)$ to $5.3080\times 10^{-5}$ for $R(0.4)$, an improvement by roughly a factor of 498. Refining again gives $R(0.2)\approx 0.999996670632607$, whose absolute error is about $3.3294\times 10^{-6}$. The refined truncation errors decrease by nearly four for $A$ and nearly sixteen for $R$, reflecting their second and fourth orders.

The logarithmic scale on each axis turns power laws into straight lines. The dashed reference curves are $h^2/6$ and $h^4/480$, the magnitudes of the leading truncation errors. The plotted errors are computed with 70-digit decimal arithmetic, rather than clipped to a display floor; this isolates the asymptotic expansion from roundoff error.

Worked example: integrating an exponential. Approximate the definite integral of the exponential function on $[0,1]$:For numerical integration, the composite trapezoidal rule adds the areas of trapezoids between successive samples; this is the quadrature use of the endpoint average that also occurs in the ODE trapezoidal rule. On $n$ equal intervals, with $h=1/n$, defineSumming the geometric series gives $T_n=(e-1)\frac{h}{2}\frac{e^h+1}{e^h-1}$. Expanding the exponential function near zero yieldsThe leading truncation error again has $p=2$, $q=2$. On the uniform nested grids with $n$ and $2n$ intervals, Richardson extrapolation therefore givesThis linear combination is exactly composite Simpson's rule on the finer grid, whose spacing is $h/2$. On each coarse panel, an old endpoint receives weight $h/6$ and the new midpoint weight $2h/3$; shared old endpoints receive weight $h/3$. These are the usual Simpson's rule weights $1,4,2,\dots ,4,1$ multiplied by $h/6$. The equivalence is explained directly in LeMesurier's university notes.^[ref]

For two coarse panels and four fine panels,The absolute errors are about $0.0356493$, $0.00894008$ and $0.0000370135$, respectively. Reusing the fine-grid samples makes Richardson extrapolation especially attractive here: the resulting Simpson's rule needs no samples beyond those already used by $T_{2n}$.

When the improvement is justified. Richardson extrapolation requires the stated asymptotic expansion and the correct positive $p$. If the actual leading exponent is $r\ne p$, its coefficient after combination is $c(2^{p-r}-1)/(2^p-1)$, so the leading truncation error generally remains. Merely knowing $A(h)-L=O(h^p)$ does not supply a common coefficient $c$ or a higher-order remainder. A discontinuity of a function, a singular endpoint, or unrelated changes between grids can invalidate the assumed asymptotic expansion; refinement alone does not guarantee improvement for every numerical problem.

Roundoff error and errors in the sampled values survive the cancellation of truncation error. If the coarse and fine values have absolute perturbations bounded by $\epsilon$, the perturbation in $R(h)$ is bounded by $(2^p+1)\epsilon /(2^p-1)$; for $p=2$ this is $5\epsilon /3$. In floating-point arithmetic, a centered difference quotient can also amplify sample errors through division by $h$, so an indefinitely smaller $h$ need not be more accurate. Persson's notes describe this balance between truncation error and roundoff error.^[ref]

The same cancellation idea appears in step-doubling error estimation. For an order-$p$ one-step method for an ordinary differential equation, two half steps each contribute local truncation error of order $h^{p+1}$, so their accumulated leading local error has ratio $2^{-p}$ to one full step. This explains the denominator $2^p-1$ there; the appropriate exponent follows from that local error model, rather than automatically from a generic use of Richardson extrapolation.