Calculus×Computing
ES

Sequences

Level FundamentalDifficulty ★★★★★Concept⌖ Open in the map

What is it?

An infinite list a1,a2,a3,…a_1, a_2, a_3, \dots — a function ℕ→ℝ\N \to \R. Every iterative algorithm produces one: the successive guesses of Newton's method, the losses of a training run, the cost T(n)T(n) of an algorithm on inputs of size nn.

Formulas

an=1n,an+1=12(an+2an)a_n = \frac{1}{n}, \qquad a_{n+1} = \frac12\left(a_n + \frac{2}{a_n}\right)
explicit and recursive (the second converges to 2\sqrt 2)

Where it shows up in computing

  • Scientific computing★★★★★frequentScientific computing and algorithms

    Iterative solvers produce a sequence of approximations xkx_k that should converge to the answer.

  • Algorithm analysis and complexity★★★★★frequentScientific computing and algorithms

    The running time T(n)T(n) is a sequence, often defined by a recurrence such as T(n)=2T(n/2)+nT(n) = 2T(n/2) + n.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

λ Scientific computing and algorithms

ℒ AI and machine learning

3D Computer graphics

⚙ Robotics and control

⚛ Physics and simulation

∿ Signals, media and vision

⊕ Cryptography and security

ψ Quantum computing and physics

⇄ Optimization and systems

What depends on it

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.

↑ ↓ to navigate · ↵ · Esc