Week 2 – Models of Computation, O-Notation, Karatsuba, Maximum Subarray Sum

Sources & reconstruction notes

• Lecture 2 (Püschel): Unit-cost RAM model, asymptotic analysis and O-notation, Karatsuba multiplication, motivation for maximum subarray sum.
• Lecture 3 (first hour): O-notation recap and “abuse of notation”, the Maximum-Subarray-Sum problem, Algorithms 1 ($\Theta (n^3)$) and 2 ($\Theta (n^2)$), start of divide and conquer.
• No script chapter was provided for this week, so there is no script numbering to follow. Section numbers below are my own.
• Missing material:
  1. In Lecture 2, the part right after the break is garbled (only fragments like “nochmal ableiten … 6n … also gilt. Allgemein”). §3.4 reconstructs it as the standard polynomial-vs-exponential l’Hôpital example. ⚠ Reconstruction.
  2. In Lecture 3, the entire second hour is missing. The recording contains only noise (“Thank you” captions) after the three cases of divide and conquer were stated. §3.8 completes the divide-and-conquer algorithm the standard way. ⚠ Reconstruction: check it against Püschel’s handwritten notes on Moodle.
• The stock-price example array (8 values) cannot be recovered from the transcript. Only the optimum, 29, is certain. §4 uses my own example arrays instead.

---

1. Executive Overview & Core Objectives

Week 1 counted elementary operations exactly. This week makes such counts machine-independent. The unit-cost random-access model (Unit-Cost-RAM-Modell) defines what an operation is. Asymptotic analysis (asymptotische Laufzeitanalyse) with O-notation (O-Notation) removes the constant factors that differ between machines and keeps only the growth (Wachstum). Two algorithms then show this in action. Karatsuba’s algorithm multiplies $n$-digit numbers with $n^{{\log }_{2}3}\approx n^{1.58}$ digit multiplications instead of $n^2$, through divide and conquer and a recurrence. For the Maximum Subarray Sum problem, removing repeated computation takes the naive $\Theta (n^3)$ algorithm down to $\Theta (n^2)$, and divide and conquer is introduced as the next design idea.

Learning objectives. After this week you should be able to:

• Describe the unit-cost RAM model and explain why model runtime and real runtime differ only by a constant factor.
• State the course’s definition of $O(f)$ precisely, including the role of the domain $\mathcal{N}\subseteq \mathbb{N}$ and the codomain ${\mathbb{R}}^{+}$.
• Prove or disprove $g\in O(f)$ with an explicit constant $c$, with the quotient criterion, or with limits and l’Hôpital.
• Simplify O-expressions: drop constants and lower-order terms, and ignore logarithm bases.
• Explain the “abuse of notation” $f\le O(g)$, and what $\Theta$ (“same order”) expresses.
• Derive Karatsuba’s identity, set up the recurrence $T(n)=3T(n/2)$, solve it by telescoping, and convert $3^{{\log }_{2}n}$ to $n^{{\log }_{2}3}$.
• Define the Maximum Subarray Sum problem, analyse the naive algorithm with matching upper and lower bounds ($\Theta (n^3)$), and give the improved $\Theta (n^2)$ algorithm.
• Turn nested loops into sums, and check index ranges with the “plug in the boundary” trick.
• Name the three cases of the divide-and-conquer approach to maximum subarray sum.

---

2. Core Concepts & Formal Definitions

2.1 The problem: what is “runtime”?

The runtime of an implemented algorithm depends on:

• the input (Eingabe): different inputs of the same size can take different time;
• the computer: speeds have changed enormously over the last 40+ years;
• the implementation: programming language (Python, C, Rust), compiler, and how cleverly it is written.

Yet results from algorithm analysis stay valid for decades. That needs an abstraction (Abstraktion) that satisfies two conditions:

1. it removes machine and implementation details, and
2. it still says something informative (“algorithm A is good, B is bad” would be too coarse).

The two ingredients are (A) the computation model (Berechnungsmodell), the unit-cost RAM model, and (B) asymptotic runtime analysis (asymptotische Laufzeitanalyse).

2.2 The unit-cost random-access model

Definition (Unit-cost random-access model / Unit-Cost-RAM-Modell)

A computer consists of a memory (Speicher) and a processor (Prozessor).

• Memory: a linear list of memory cells (Speicherzellen). Each cell is either empty or contains a number.
• Random access (beliebiger Zugriff): the processor can access any cell, and every access costs the same.
• Processor: executes elementary operations (elementare Operationen):
  • reading and writing data (memory access),
  • arithmetic: $+,-,\times ,/,\dots$,
  • comparisons: $<,>,\le ,==,\dots$,
  • and some more.
• Unit cost: every elementary operation costs 1.
• Runtime in the model (Laufzeit) := the number of elementary operations executed.

Real machines are more complicated (memory hierarchy, caches). According to the lecture this “changes nothing essential” for this course’s analyses.

Key observation (model vs. reality)

Model runtime (a count such as $7n^2$) and measured program runtime (seconds) differ essentially by a constant factor. Each real operation takes between some minimum and some maximum time, e.g. 1–3 ns for an addition. Then
$\text{measured time}\approx \text{const}\cdot \#\text{operations},\text{const}\in [1,3]\cdot 10^{-9}\text{s}.$
Faster computers only change this constant. The growth of the operation count never changes. (Quantum computers are explicitly excluded.)

Principle (universal runtime analysis)

1. Count elementary operations in the model.
2. Ignore constant factors: $n^2$ and $17n^2$ operations are “the same”.
3. Consider only growth, i.e. the fastest-growing term.

Examples: $2n^2-n$ → only $n^2$ matters (quadratic). $7n+\log n$ → only $n$ matters (linear).

Abbreviations Püschel uses on the board: Ops = operations, Algo = algorithm, Mult = multiplication, Bsp = Beispiel (example).

2.3 O-notation

Definition (O-notation, course version)

Let $\mathcal{N}\subseteq \mathbb{N}$ be the set of possible input sizes (mögliche Eingabegrößen), typically $\mathcal{N}=\{n_0,n_0+1,\dots \}$. Let ${\mathbb{R}}^{+}$ be the strictly positive reals ($0\notin {\mathbb{R}}^{+}$). For $f:\mathcal{N}\to {\mathbb{R}}^{+}$ define
$O(f):=\{g:\mathcal{N}\to {\mathbb{R}}^{+}|\exists c>0\forall n\in \mathcal{N}:g(n)\le c\cdot f(n)\}.$

Equivalent formulations:
$g\in O(f)⟺\frac{g}{f}\text{ is bounded on }\mathcal{N}⟺g\text{ grows asymptotically not faster than }f.$

In words: $O(n^2)$ is the set of all functions that grow at most quadratically.

Remarks on the definition:

• $O(f)$ is a set of functions. Grouping all functions with at most the same growth into one set is exactly what produces the abstraction.
• The constant $c$ is existentially quantified. That is how constant factors disappear: they get absorbed into $c$.
• Why $\mathcal{N}$ instead of $\mathbb{N}$? Some functions are not defined, or not positive, at small $n$, so we let the domain start later.
  • $f(n)=n^2-3n$ is negative for $n=1,2$ and $0$ at $n=3$. Choose $n_0=4$.
  • $f(n)={\log }_2({\log }_{2}n)$: at $n=1$ it is ${\log }_{2}0$ (undefined), at $n=2$ it is ${\log }_{2}1=0\notin {\mathbb{R}}^{+}$. Start at $n_0=3$.
  • In star search (week 1) the input sizes started at $n=2$.
• The starting point is irrelevant for asymptotics. Only growth for large $n$ matters. If the beginning is a problem, start later.
• Other courses and books use variants, e.g. "$\exists c,n_0:\forall n\ge n_0:g(n)\le cf(n)$". Püschel says these are essentially all equivalent. Here $n_0$ is built into the domain $\mathcal{N}$.

Definition (Abuse of notation / Missbrauch der Notation), Lecture 3

Instead of $f(n)\in O(g(n))$ the course often writes
$f(n)\le O(g(n)).$
Strictly, "$\le$" between a function and a set is undefined. It is a convenient, intuitive convention (“by abuse of notation”), and mathematicians do it too. Many textbooks write $f=O(g)$ instead.

Preview: $\Theta$ ("same order"), formally introduced on the next exercise sheet

If both $g\in O(f)$ and $f\in O(g)$, then $g$ has exactly the growth of $f$:
$g\in \Theta (f):⟺g\in O(f)\text{and}f\in O(g).$
We say $g$ and $f$ have the same order (gleiche Ordnung). Example: $A(n)\le O(n^3)$ and $n^3\le O(A(n))$ give $A(n)=\Theta (n^3)$.

2.4 Tools for working with O

Lemma (constant factors)

For every constant $a\in {\mathbb{R}}^{+}$: $O(f)=O(a\cdot f)$.
Proof sketch: if $g\le cf$, then $g\le (c/a)(af)$; conversely, if $g\le c(af)$, then $g\le (ca)f$. $■$ (Not proved in the lecture.)

Lemma (limit criterion), connecting O-notation to exercise sheets 0/1

Let $f,g:\mathcal{N}\to {\mathbb{R}}^{+}$.

1. If $\underset{n\to \infty }{\lim }\frac{g(n)}{f(n)}=\infty$, then $g$ grows asymptotically faster than $f$, and $g\notin O(f)$.
2. If $\underset{n\to \infty }{\lim }\frac{g(n)}{f(n)}=L\in \mathbb{R}$ (a finite limit exists), then $g\in O(f)$.

Exam Trap: the limit criterion is sufficient, not necessary

The limit does not have to exist for $g\in O(f)$. Example: $g(n)=(2+\sin n)n$ and $f(n)=n$. Then $g/f=2+\sin n$ has no limit, but it is bounded by $3$, so $g\in O(f)$ with $c=3$. If the limit does not exist, go back to the definition (show $g/f$ is bounded).

Lemma (l'Hôpital's rule, school version)

If $\lim g(x)=\lim f(x)=\infty$ (or both $=0$), and $f,g$ are differentiable with $f^{\prime }(x)\ne 0$ for large $x$, then
${\lim }_{x\to \infty }\frac{g(x)}{f(x)}={\lim }_{x\to \infty }\frac{g^{\prime }(x)}{f^{\prime }(x)},$
provided the right-hand limit exists. To differentiate, treat $n$ as a real variable $x$.

Lemma (logarithm bases are irrelevant)

For bases $a,b>1$:
${\log }_{a}n=\frac{{\log }_{b}n}{{\log }_{b}a}={\log }_{b}n\cdot {\log }_{a}b.$
So logarithms to different bases differ only by the constant factor ${\log }_{a}b$, which gives $O({\log }_{a}n)=O({\log }_{b}n)$. From now on we write only $\log$, with no base.

⚠ Transcript garble: the formula was transcribed as "${\log }_{a}n={\log }_{b}n\cdot {\log }_{b}a$". That has the wrong base in the second factor. The correct factor is ${\log }_{a}b=1/{\log }_{b}a$, as above.

Lemma (useful power identity, used for Karatsuba)

For $a,b>0$, $b\ne 1$:
$a^{{\log }_{b}n}=n^{{\log }_{b}a}.$
Proof: take ${\log }_b$ of both sides. Left: ${\log }_{b}n\cdot {\log }_{b}a$. Right: ${\log }_{b}a\cdot {\log }_{b}n$. These are equal, and ${\log }_b$ is injective. $■$

2.5 O-notation for simplification

In practice O-notation is used to simplify. One never writes the left-hand forms below:

Never write	Write instead	Reason
$O(2n^2-3n)$	$O(n^2)$	drop the constant and the slower term $3n$
$O(7n-{\log }_{2}n+{\log }^{2}n)$	$O(n)$	$\log n$ and ${\log }^{2}n$ grow slower than $n$
$O({\log }_{7}n)$	$O(\log n)$	the base only contributes a constant
$O(3n^3+2n^2+17)$	$O(n^3)$	dominant term only

These are equal as sets, which is why the simplified form is allowed.

The most common classes in this course:
$O(1)\subset O(\log n)\subset O(n)\subset O(n\log n)\subset O(n^2)\subset O(n^3)\subset \dots$
Between them sit e.g. ${\log }^{2}n,{\log }^{3}n$ (between $\log n$ and $n$). Note that $O(n^2)$ contains $n$, $\log n$, $n\log n$: everything that grows at most quadratically.

Why logarithms appear so often

Many algorithms repeatedly halve the problem. Halving $n$ until only 1 is left takes about ${\log }_{2}n$ steps, so logarithms show up in many cost analyses.

2.6 Integer multiplication

Problem (multiplication of integers / Multiplikation ganzer Zahlen)

Given: two $n$-digit integers. Find: their product.
Elementary operation: a digit multiplication (Ziffernmultiplikation), i.e. one single-digit × single-digit product. Additions and shifts by powers of 10 are not counted here.
Motivation: hardware multiplies only integers of bounded size. Arbitrarily long integers need an algorithm.

2.7 Maximum Subarray Sum

Problem (Maximum Subarray Sum / maximale Teilsumme)

Given: $a_1,\dots ,a_n\in \mathbb{Z}$ (positive and negative).
Subarray sums (Teilsummen): for $1\le i\le j\le n$,
$S_{ij}:={\sum }_{k=i}^j{a}_k=a_i+a_{i+1}+\cdots +a_j.$
($j\ge i$; for $j=i$ the sum is the single number $a_i$.)
Find: the maximum subarray sum
$S^{\ast }:=\max (0,{\max }_{1\le i\le j\le n}{S}_{ij}).$
The $0$ is the empty subarray: if all $a_i<0$, the best action is to do nothing, so $S^{\ast }=0$.
Elementary operation: addition.

Motivation (stock prices / Aktienkurs): $a_t$ is the daily change of a share’s price. With a time machine, which buy and sell days maximise profit? Buying at the start of day $i$ and selling at the end of day $j$ gives profit $S_{ij}$. With 8 numbers you can solve it by inspection. In the lecture the optimum was 29, and the audience needed several attempts: 7, 23, 28, then extending the holding period gave 29. With $10^6$ numbers, inspection is hopeless. One heuristic from the lecture: buying just before a negative change never makes sense.

Definition (Pseudocode)

Pseudocode uses programming constructs (loops, assignments) without being a real programming language. Its exact form can vary.

Definition (Divide and conquer / Teile und herrsche)

A recursive design principle (Entwurfsprinzip):

1. Divide: split the problem into subproblems (often two halves).
2. Conquer: solve the subproblems recursively.
3. Combine: assemble the overall solution from the partial solutions.

This only works if the subproblem solutions are related to the overall solution. It can always be tried as an approach; sometimes it works, sometimes not.

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 Example A: $n^2$ vs. $4n^2$

Let $f(n)=n^2$ and $g(n)=4n^2$ on $\mathcal{N}=\mathbb{N}$.

• $f\in O(g)$? Yes. Choose $c=1$: $n^2\le 1\cdot 4n^2$ for all $n$. (Any $c\ge 1/4$ works.)
• $g\in O(f)$? Yes. Choose $c=4$: $4n^2\le 4\cdot n^2$ for all $n$.

So $O(n^2)=O(4n^2)$, an instance of the constant-factor lemma.

⚠ Discrepancy: in the recording the constant for "$g\in O(f)$" was given as “ein Viertel” ($1/4$). That is wrong: $4n^2\le \frac{1}{4}{n}^2$ is false. The correct choice is $c=4$ (or larger). $c=1/4$ is the smallest valid constant for the other direction, $f\le cg$, which is probably where the mix-up came from.

3.2 Example B: is $0.001n^2\in O(n^{1.6})$?

No. Quotient criterion:
$\frac{g(n)}{f(n)}=\frac{0.001n^2}{n^{1.6}}=0.001\cdot n^{0.4}\stackrel{n\to \infty }{\to }\infty .$
The quotient is unbounded, so there is no constant $c$ with $0.001n^2\le c{n}^{1.6}$ for all $n$. The small constant $0.001$ does not help, because constants never beat growth.

⚠ Transcript: the quotient was first written incorrectly (”$0.01/n^{0.4}$… nein, falsch”) and corrected to $0.001\cdot n^{0.4}$.

Exam Trap: wrong argument from a common superset

A student argued “both are in $O(n^2)$, so one is in O of the other”. Wrong. Being in a common larger class says nothing about mutual containment. Every polynomial lies in $O(10^{6n})$, but that does not make all polynomials $O$ of each other. Also: $n\in O(n^2)$ but $n^2\notin O(n)$. ”$g$ grows not faster than $f$” does not mean ”$f$ grows faster than $g$”; they may grow equally fast.

3.3 Example C: $\ln n\in O(n^a)$ for every $a>0$

Even for tiny $a$ (e.g. $a=0.001$), the logarithm is eventually dominated. Both numerator and denominator tend to $\infty$, so l’Hôpital applies:

$$\underset{n\to \infty }{\lim }\frac{\ln n}{n^a}\stackrel{\text{l’H}}{=}\underset{n\to \infty }{\lim }\frac{1/n}{a{n}^{a-1}}=\underset{n\to \infty }{\lim }\frac{1}{a{n}^a}=0,$$

where the last step uses $a>0$. The limit $0$ is finite, so by the limit criterion $\ln n\in O(n^a)$. Since ${\log }_{b}n=\ln n/\ln b$, the same holds for every ${\log }_{b}n$ with $b>1$.

⚠ Transcript: the derivative of $n^a$ was transcribed as “a hoch n minus 1”. It is $a\cdot n^{a-1}$.

Why not substitute $x=\ln n$? A student suggested $n=e^x$. Püschel cautioned that such substitutions “can cause problems” with O-notation, because the domain changes from integers to the values $\ln n$. The direct l’Hôpital route is cleaner.

3.4 Example D: polynomials vs. exponentials (⚠ reconstruction)

The fragment after the break (“nochmal ableiten … $6n$ … also gilt. Allgemein …”) fits the standard example "$n^3\in O(2^n)$" (or $O(e^n)$), shown by applying l’Hôpital three times:

$$\underset{n\to \infty }{\lim }\frac{n^3}{e^n}\stackrel{\text{l’H}}{=}\lim \frac{3n^2}{e^n}\stackrel{\text{l’H}}{=}\lim \frac{6n}{e^n}\stackrel{\text{l’H}}{=}\lim \frac{6}{e^n}=0.$$

General statement: $n^k\in O(b^n)$ for every constant $k$ and every $b>1$. Apply l’Hôpital $k$ times: each step lowers the power by one, while $(b^n{)}^{\prime }=\ln b\cdot b^n$ keeps its form. Every polynomial grows slower than every exponential.

3.5 Karatsuba’s identity

School method on $62\cdot 37$. Name the digits $a=6$, $b=2$ (first number) and $c=3$, $d=7$ (second number):

• $b\cdot d=2\cdot 7=14$,
• $b\cdot c=2\cdot 3=6$, shifted by one position,
• $a\cdot d=6\cdot 7=42$, shifted by one position,
• $a\cdot c=6\cdot 3=18$, shifted by two positions.

Sum: $14+60+420+1800=2294$. 4 digit multiplications. In general, two $n$-digit numbers need $n^2$ digit multiplications.

What the school method computes. The numbers are $10a+b$ and $10c+d$, and the shifts are the powers of 10:

$$(10a+b)(10c+d)=bd+10(bc+ad)+100ac.\text{\hspace{1em}(School)}$$

Karatsuba’s version:

$$(10a+b)(10c+d)=bd+10bd+10(a-b)(d-c)+10ac+100ac.\text{\hspace{1em}(Karatsuba)}$$

Only 3 distinct multiplications occur: $bd$, $(a-b)(d-c)$, $ac$. Each of $bd$ and $ac$ is computed once and written twice. Subtractions are cheap and not counted.

Proof that the two agree (Püschel: “10th-grade school mathematics”). Expand the middle product:

$$(a-b)(d-c)=ad-ac-bd+bc.$$

So the bracket multiplied by $10$ in (Karatsuba) is

$$bd+(ad-ac-bd+bc)+ac=ad+bc.$$

The $+bd$ cancels against $-bd$, and $+ac$ against $-ac$. Hence (Karatsuba) $=bd+10(ad+bc)+100ac=$ (School). $■$

Check on the example: $bd=14$, $(a-b)(d-c)=(6-2)(7-3)=4\cdot 4=16$, $ac=18$:

$$14+140+160+180+1800=2294.✓$$

Three multiplications instead of four.

3.6 Generalisation to $n$ digits

The cancellation does not depend on the number $10$. It works with any base, in particular $10^{n/2}$. Let $x,y$ be $n$-digit numbers ($n$ even). Split each in the middle:

$$x=10^{n/2}A+B,y=10^{n/2}C+D,$$

where $A,C$ are the left (high) halves and $B,D$ the right (low) halves, each with $n/2$ digits. (Just like $62=10\cdot 6+2$.) Then

$$\begin{array}{rlrl}x\cdot y& =BD+10^{n/2}(BC+AD)+10^{n}AC& & \text{(school)}\\ & =BD+10^{n/2}BD+10^{n/2}(A-B)(D-C)+10^{n/2}AC+10^{n}AC.& & \text{(Karatsuba)}\end{array}$$

The same cancellations happen as before: $10^{n/2}BD$ against $10^{n/2}(-BD)$, and $10^{n/2}AC$ against $10^{n/2}(-AC)$.

Key algorithmic consequence

Two $n$-digit numbers can be multiplied with three multiplications of $n/2$-digit numbers, namely $BD$, $AC$, $(A-B)(D-C)$, plus additions, subtractions and shifts (multiplying by $10^{n/2}$ just appends zeros). Each of the three products is again computed recursively in the same way. This is divide and conquer.

Details:

• Odd $n$: pad with a leading zero. This does not change the analysis.
• $A-B$ and $D-C$ can be negative, with absolute value $<10^{n/2}$. They are still (signed) $n/2$-digit numbers. The lecture did not discuss signs; an implementation handles them separately.
• Additions are not counted in the lecture’s analysis, where only digit multiplications matter. Each level also does $O(n)$ digit additions. One can show this does not change the final $O(n^{{\log }_{2}3})$ bound, but that was not part of the lecture.

3.7 Analysis of Karatsuba: recurrence, telescoping, closed form

Simplifying assumption: $n=2^k$, so we can keep halving down to 1 digit. Otherwise pad with zeros up to the next power of two, which changes nothing asymptotically. The course often makes such assumptions: edge cases matter for a correct implementation but not for understanding the analysis.

Let $T(n)$ be the number of digit multiplications Karatsuba uses for two $n$-digit numbers.

• Base case: two 1-digit numbers need one digit multiplication, so $T(1)=1$.
• Recurrence: three recursive multiplications of $n/2$-digit numbers:
  $T(n)=3T(n/2)(n>1).$

Telescoping (substitute the recurrence into itself):

$$\begin{array}{rl}T(n)& =3T(n/2)\\ & =3\cdot 3T(n/4)=3^{2}T(n/2^2)\\ & =3^{3}T(n/2^3)\\ & ⋮\\ & =3^{j}T(n/2^j).\end{array}$$

Pattern: denominator $2^j$ goes with factor $3^j$. We reach the base case $T(1)$ when $n/2^j=1$, i.e. $j=k$:

$$T(n)=3^{k}T(1)=3^k.$$

Proof by induction (the guess is only a conjecture until proved). Claim: $T(2^k)=3^k$ for all $k\ge 0$.

• IA ($k=0$): $T(1)=1=3^0$. ✓
• IS ($k\to k+1$): $T(2^{k+1})=3T(2^k)\stackrel{\text{IH}}{=}3\cdot 3^k=3^{k+1}$. ✓ $■$

Expressing it in $n$. With $k={\log }_{2}n$ and the power identity $a^{{\log }_{b}n}=n^{{\log }_{b}a}$:

$$T(n)=3^{{\log }_{2}n}=n^{{\log }_{2}3}\approx n^{1.585}.$$

Comparison for $n=1000$:

Method	Digit multiplications	$n=1000$
School method	$n^2$	$10^6$
Karatsuba	$n^{{\log }_{2}3}\approx n^{1.585}$	$\approx 5.7\cdot 10^4$

There is no bad constant in front, so the algorithm is also fast in practice. It is $O(n^{1.585})$.

Why 3 instead of 4 matters so much

Naive divide and conquer with the school formula needs 4 half-size products: $T(n)=4T(n/2)$ gives $4^{{\log }_{2}n}=n^2$, so no gain at all. Saving one multiplication per level compounds over ${\log }_{2}n$ levels: $(3/4{)}^{{\log }_{2}n}=n^{{\log }_{2}3-2}$. See Self-Assessment Q4.

History (from the lecture). Until about 1960, $n^2$ was believed optimal. At a seminar, the famous mathematician Kolmogorov presented ideas for proving this lower bound. A 23-year-old student in the audience, Karatsuba, sent him a faster method about three weeks later, and Kolmogorov was “shocked”. Kolmogorov wrote up the paper himself and submitted it with Karatsuba as author. It appeared in 1962; Karatsuba learned he had a publication only when it came out. (Background beyond the lecture: the 1962 paper lists A. Karatsuba and Yu. Ofman as authors.)

Geht es besser? Yes. Once people saw that improvement was possible, they paid attention to the problem. There are algorithms with $O(n\log n\log \log n)$ (with sizable constants), and with $O(n\log n)$, whose constants are so enormous that they are not practically relevant. (Names, not given in the lecture: Schönhage–Strassen, 1971; Harvey–van der Hoeven, 2019.)

3.8 Maximum Subarray Sum: Algorithm 1 (naive, try everything)

Idea: compute all $S_{ij}$ and remember the best. There is no algorithmic idea in it: just try everything. “Try everything” is often an algorithm, and often not the best one.

MaxSubarray1(a_1, ..., a_n):
    best := 0                          // empty subarray
    for i := 1 to n:                   // all start points
        for j := i to n:               // all end points (end >= start)
            S := a_i + a_{i+1} + ... + a_j     // computed from scratch
            if S > best: best := S
    return best

Unrolled inner loop for a fixed $i$:

$$\begin{array}{rlrl}{S}_{ii}& =a_i& & 0\text{ additions}\\ S_{i,i+1}& =a_i+a_{i+1}& & 1\\ S_{i,i+2}& =a_i+a_{i+1}+a_{i+2}& & 2\\ & ⋮& & \\ S_{in}& =a_i+a_{i+1}+\cdots +a_n& & n-i\end{array}$$

Off-by-one check ("plug in the boundary")

Is the last count $n-i$, $n-i-1$ or $n-i+1$? Plug in $i=n$: then $S_{nn}=a_n$ is a single number, so $0$ additions. Only $n-i$ gives $0$ at $i=n$, so $n-i$ is correct.

Cost for a fixed $i$:

$$0+1+\cdots +(n-i)=\frac{(n-i)(n-i+1)}{2}.$$

(Gauss’s formula for the first $n-i$ natural numbers: middle-of-the-night knowledge. “If you have to ask an AI tool for this, something has gone wrong.”)

Sandwich bounds to make the summation easy. We want squares:

$$\frac{(n-i{)}^2}{2}\le \frac{(n-i)(n-i+1)}{2}\le \frac{(n-i+1{)}^2}{2}.$$

Left: we decreased the factor $(n-i+1)$ to $(n-i)$. Right: we increased $(n-i)$ to $(n-i+1)$. Estimating early is legitimate because the final O-statement is a bound anyway. But do not overdo it: bounding by $(n-i+1{)}^{27}$ would be too crude.

Upper bound. Let $A(n)$ be the total number of additions. Loops become sums (“for $i=1$ to $n$” becomes ${\sum }_{i=1}^n$):

$$A(n)\le \sum _{i=1}^n\frac{(n-i+1{)}^2}{2}.$$

Write the sum out: $i=1$ gives $n^2$, $i=2$ gives $(n-1{)}^2$, …, $i=n$ gives $1^2$. So it is the sum of the first $n$ squares (formula from the exercise sheet):

$$A(n)\le \frac{1}{2}\sum _{m=1}^n{m}^2=\frac{1}{2}\cdot \frac{n(n+1)(2n+1)}{6}=\frac{1}{6}n(n+\frac{1}{2})(n+1).$$

This is clearly cubic, so $A(n)\le O(n^3)$ directly. In slow motion: $n+\frac{1}{2}\le 2n$ and $n+1\le 2n$ for $n\ge 1$, so

$$A(n)\le \frac{1}{6}\cdot n\cdot 2n\cdot 2n=\frac{2}{3}{n}^3\le n^3.$$

Is the upper bound tight? $A(n)\le O(n^5)$ is also true but useless (“too generous”). Maybe the true growth is only quadratic and the estimate was sloppy? To rule that out we need a lower bound.

Lower bound:

$$A(n)\ge \sum _{i=1}^n\frac{(n-i{)}^2}{2}=\frac{1}{2}[(n-1{)}^2+(n-2{)}^2+\cdots +1^2+0^2]=\frac{1}{2}\sum _{m=1}^{n-1}{m}^2.$$

This differs from the upper bound by exactly the term $n^2$ (times $\frac{1}{2}$). With the formula for $n-1$:

$$A(n)\ge \frac{1}{2}\cdot \frac{(n-1)n(2n-1)}{6}=\frac{1}{6}(n-1)n(n-\frac{1}{2}).$$

Use $n-1\ge \frac{n}{2}$ (for $n\ge 2$) and $n-\frac{1}{2}\ge \frac{n}{2}$ (for $n\ge 1$):

$$A(n)\ge \frac{1}{6}\cdot \frac{n}{2}\cdot n\cdot \frac{n}{2}=\frac{1}{24}{n}^3(n\ge 2).$$

Hence $n^3\le 24A(n)$, i.e. $n^3\le O(A(n))$.

⚠ Transcript garble: the second estimate was transcribed as ”$n$ minus 1 halb ist auch größer gleich 1 halbe”. The intended estimate is $n-\frac{1}{2}\ge \frac{n}{2}$.

Conclusion:

$$\frac{1}{24}{n}^3\le A(n)\le \frac{2}{3}{n}^3⟹A(n)=\Theta (n^3).$$

The naive algorithm is exactly cubic, no better. (Exact value, for checking: $A(n)=\frac{(n-1)n(n+1)}{6}$; see Self-Assessment Q5.)

Practical meaning: $n=1000$ gives $\approx 10^9$ additions, about 0.1 s on a smartphone. $n=10^6$: “Ende der Fahnenstange”, no result in reasonable time.

Two practical tips from the lecture

1. Loops become sums. Nested loops become nested sums; then evaluate them.
2. When stuck on a sum, write it out. The pattern (e.g. “sum of the first $n$ squares”) becomes visible. With practice you can manipulate sums directly.

Exam Trap: which bound for O?

For an O-statement (worst-case upper bound) use the upper estimate. Lower bounds alone are trivially easy and useless (“runtime $\ge 0$”). Lower bounds matter only to show that an upper bound is tight (giving $\Theta$).

3.9 Maximum Subarray Sum: Algorithm 2 (no repeated computation)

Observation (student): $S_{i,i+1}$ computes $a_i+a_{i+1}$, and $S_{i,i+2}$ computes $a_i+a_{i+1}$ again. The same addition is done multiple times.

Idea: no repeated computation (keine Mehrfachberechnungen). Each sum extends the previous one by one element:

$$S_{i,j}=S_{i,j-1}+a_j.$$

MaxSubarray2(a_1, ..., a_n):
    best := 0
    for i := 1 to n:
        S := a_i                         // S_{i,i}: 0 additions
        if S > best: best := S
        for j := i+1 to n:
            S := S + a_j                 // S_{i,j} = S_{i,j-1} + a_j: 1 addition
            if S > best: best := S
    return best

Ops per $i$: $0,1,1,\dots ,1$, i.e. $n-i$ additions in total (boundary check: $i=n$ gives $0$ ✓).

$$A(n)=\sum _{i=1}^n(n-i)=(n-1)+(n-2)+\cdots +1+0=\frac{n(n-1)}{2}=\Theta (n^2).$$

We saved a whole polynomial order: $n^3\to n^2$.

Memory (Speicher), a student question

“Don’t we now have to store all the $S$ values?” No. One variable $S$ is overwritten in each step, plus the best value so far, so the extra memory is $O(1)$. In general the remark is valid: besides operations, algorithms are also judged by memory usage and data movement. These are sometimes analysed, but rarely in this course.

Püschel’s comment: Algorithm 2 needs no algorithms course; a bit of thinking suffices. There is no real design principle behind it. Since quadratic growth is still too slow for many practical problems, we ask again: Geht es besser?

3.10 Maximum Subarray Sum: divide and conquer

Covered in the lecture. Split $a_1,\dots ,a_n$ into a left half ($n/2$ elements) and a right half ($n/2$ elements). The optimal subarray falls into exactly one of three cases:

1. Case 1, entirely left: the recursive solution on the left half gives the answer.
2. Case 2, entirely right: the recursive solution on the right half gives the answer.
3. Case 3, across the middle (“über die Mitte”): the “unpleasant” case. Solving left and right separately does not find it.

If only cases 1 and 2 existed, we would solve both halves and take the better one. Case 3 needs extra thought.

⚠ The recording ends here. Everything below is a reconstruction of the standard continuation, not lecture content. Compare with the handwritten notes.

Handling case 3 (standard). A subarray crossing the middle is a suffix of the left half plus a prefix of the right half, and the two parts can be optimised independently:

$$\text{best crossing sum}=\underset{\text{best suffix of left half}}{\underbrace{\underset{i\le n/2}{\max }\sum _{k=i}^{n/2}{a}_k}}+\underset{\text{best prefix of right half}}{\underbrace{\underset{j>n/2}{\max }\sum _{k=n/2+1}^j{a}_k}}.$$

Both maxima can be computed incrementally, as in Algorithm 2 (extend by one element per step), with about $n/2$ additions each, so about $n$ in total.

MaxSubarrayDC(a_l, ..., a_r):          // reconstruction
    if l == r: return max(0, a_l)
    m := floor((l + r) / 2)
    L := MaxSubarrayDC(a_l, ..., a_m)          // Case 1
    R := MaxSubarrayDC(a_{m+1}, ..., a_r)      // Case 2
    // Case 3: best suffix of left half + best prefix of right half
    S := 0; bestSuf := 0
    for i := m downto l:   S := S + a_i;  bestSuf := max(bestSuf, S)
    S := 0; bestPre := 0
    for j := m+1 to r:     S := S + a_j;  bestPre := max(bestPre, S)
    return max(L, R, bestSuf + bestPre)

Allowing empty suffixes and prefixes (value 0) is consistent with $S^{\ast }\ge 0$.

Analysis (reconstruction). Let $n=2^k$ and $T(n)$ = number of additions. $T(1)=0$, and $T(n)\le 2T(n/2)+n$. Telescoping:

$$T(n)\le 2T(n/2)+n\le 4T(n/4)+2n\le 8T(n/8)+3n\le \cdots \le 2^{k}T(1)+kn=n{\log }_{2}n.$$

Induction check of $T(2^k)\le k{2}^k$: IA: $T(1)=0$ ✓. IS: $T(2^{k+1})\le 2\cdot k{2}^k+2^{k+1}=(k+1)2^{k+1}$ ✓.
So the divide-and-conquer algorithm runs in $O(n\log n)$, better than $\Theta (n^2)$.

---

4. Worked Examples & Applications

Example: proving $g\in O(f)$ from the definition

Show $2n^2-n\in O(n^2)$ on $\mathcal{N}=\mathbb{N}$.
We need $c$ with $2n^2-n\le c{n}^2$ for all $n\ge 1$. Since $-n\le 0$: $2n^2-n\le 2n^2$. So $c=2$ works. (Note $2n^2-n\ge 1>0$ for $n\ge 1$, so $g$ maps into ${\mathbb{R}}^{+}$ as required.)

Example: choosing the domain

$f(n)=n^2-3n$ takes the values $-2,-2,0$ at $n=1,2,3$, which are not in ${\mathbb{R}}^{+}$. Take $\mathcal{N}=\{4,5,\dots \}$. Then $f(n)\ge 4>0$, and e.g. $f\in O(n^2)$ with $c=1$.

Example: Maximum Subarray Sum by hand

$a=(2,-5,4,-1,3,-6,2)$.

• Algorithm 2, row $i=3$: $S_{33}=4$, $S_{34}=3$, $S_{35}=6$, $S_{36}=0$, $S_{37}=2$. Best in this row: 6.
• Other rows never exceed 6 (e.g. row $i=1$: $2,-3,1,0,3,-3,-1$).
• Answer: $S^{\ast }=S_{35}=4-1+3=6$.
• Divide and conquer view: halves $(2,-5,4,-1)$ and $(3,-6,2)$, split after $a_4$. Best left: $4$. Best right: $3$. Crossing: best suffix of the left half $=-1+4=3$ (via $a_3,a_4$), best prefix of the right half $=3$, total $6$. The optimum is in case 3: neither half alone finds it.

Example: all negative

$a=(-3,-1,-7)$: every $S_{ij}<0$, so $S^{\ast }=0$ (empty subarray: don’t buy).

Exam Trap: constants do not rescue growth

$0.001n^2\notin O(n^{1.6})$ and $10^{6}n\in O(n)$. Constant factors are always irrelevant for membership in O-classes; only the growth rate matters.

Exam Trap: exponents inside exponentials are not constants

$O(af)=O(f)$ holds for constant factors. It does not hold for changes in an exponent: $2^{2n}=4^n\notin O(2^n)$, since $4^n/2^n=2^n\to \infty$. But $2^{n+1}=2\cdot 2^n\in O(2^n)$. Likewise, a log base is a constant factor, so it is irrelevant, but $n^{{\log }_{2}3}$ and $n^{{\log }_{3}2}$ are very different.

Exam Trap: l'Hôpital conditions

Only apply l’Hôpital to $\infty /\infty$ or $0/0$ (with differentiability). Check this every time you apply it.

Exam Trap: "Algorithm 2 needs n² memory"

It doesn’t: one running sum and one best value suffice. Distinguish operation count from memory.

---

5. Intuition & Conceptual Bridges

Intuition: O as "at most this growth class"

Think of $O(f)$ as a bucket: everything that, up to a constant, stays below $f$ forever. Constants are “machine speed” (irrelevant), lower-order terms are “noise” (irrelevant for large $n$), and growth is “the algorithm” (decisive). On any computer of the last 50 years, a $\Theta (n)$ algorithm eventually beats a $\Theta (n^2)$ algorithm, for large enough $n$.

Intuition: why Karatsuba works

The school method needs the cross term $ad+bc$, which seems to need two products. Karatsuba gets it indirectly: $(a-b)(d-c)=ad+bc-ac-bd$, and $ac,bd$ are needed anyway. One product plus “free” additions replace one multiplication. Done recursively, the saving multiplies over ${\log }_{2}n$ levels: $3^{{\log }_{2}n}$ instead of $4^{{\log }_{2}n}$.

Intuition: three levels of algorithm improvement (maximum subarray sum)

1. Try everything (Algorithm 1): correct but wasteful, $\Theta (n^3)$.
2. Remove redundancy (Algorithm 2): reuse previous sums, $\Theta (n^2)$. “Common sense”, no design principle.
3. Design principle (divide and conquer): split the problem, handle the interaction case (crossing the middle) cleverly, $O(n\log n)$ (reconstructed).

Each step asks “Geht es besser?”, the course’s central question.

Connections:

• Week 1: elementary operations, worst-case analysis, recurrences, telescoping plus induction. Karatsuba’s $T(n)=3T(n/2)$ is the first recurrence where the argument halves instead of decreasing by 1, which gives powers and logarithms instead of sums. Week 1 already used the “linear vs. quadratic” language (star search $3n-4$ vs. $n(n-1)$); now it is formal.
• Exercise sheets 0/1: limits, “grows faster than”, l’Hôpital, $\sum m^2$. These are exactly the tools for O-notation.
• Forward: $\Theta$ (and probably $\Omega$) formally on the next exercise sheet. Divide-and-conquer recurrences of the form $T(n)=aT(n/2)+\dots$ will appear repeatedly (e.g. sorting such as merge sort). Whether maximum subarray sum can be solved even faster than $O(n\log n)$ is the natural next “Geht es besser?” (probably the next lecture).

---

6. Summary & Self-Assessment Questions

Cheat Table

Topic	Key fact
RAM model	linear memory of cells, random access at equal cost, unit cost per elementary op
Model vs. reality	differ by a constant factor; machines change only the constant
$O(f)$	$\{g:\mathcal{N}\to {\mathbb{R}}^{+}\text{ with }\exists c>0\forall n:g(n)\le cf(n)\}$
Equivalent	$g/f$ bounded, i.e. $g$ grows asymptotically not faster than $f$
Limit criterion	$\lim g/f=\infty$ means $g\notin O(f)$; finite limit means $g\in O(f)$
Notation	$f\le O(g)$ means $f\in O(g)$ (abuse of notation)
$\Theta$	$g\in O(f)$ and $f\in O(g)$: same order
Constants	$O(af)=O(f)$ for $a>0$
Log bases	${\log }_{a}n={\log }_{b}n\cdot {\log }_{a}b$, so write just $\log$
Log vs. power	$\log n\in O(n^a)$ for every $a>0$
Power vs. exponential	$n^k\in O(b^n)$ for every $k$ and $b>1$
Power identity	$a^{{\log }_{b}n}=n^{{\log }_{b}a}$
Sum of squares	${\sum }_{m=1}^n{m}^2=n(n+1)(2n+1)/6$
School multiplication	$n^2$ digit multiplications
Karatsuba identity	$xy=BD+10^{n/2}[BD+(A-B)(D-C)+AC]+10^{n}AC$
Karatsuba cost	$T(1)=1$, $T(n)=3T(n/2)$, so $T(n)=n^{{\log }_{2}3}\approx n^{1.585}$
Max subarray, Algo 1	all $S_{ij}$ from scratch: $\Theta (n^3)$, with $n^3/24\le A(n)\le 2n^3/3$
Max subarray, Algo 2	$S_{ij}=S_{i,j-1}+a_j$: $n(n-1)/2=\Theta (n^2)$, $O(1)$ extra memory
Divide and conquer	cases: left, right, crossing (suffix + prefix); $O(n\log n)$ (reconstructed)
Off-by-one check	plug in the boundary (e.g. $i=n$ must give 0 additions)

Self-Assessment Questions

Question 1. Using only the definition, prove $3n^2+5n+7\in O(n^2)$ on $\mathcal{N}=\mathbb{N}$. Give an explicit constant $c$. Then decide, with justification: (a) $n\log n\in O(n^{1.5})$? (b) $2^{n+1}\in O(2^n)$? (c) $2^{2n}\in O(2^n)$?

Solution to Question 1

Main part. For $n\ge 1$: $5n\le 5n^2$ and $7\le 7n^2$. Hence
$3n^2+5n+7\le 3n^2+5n^2+7n^2=15n^2,$
so $c=15$ works. (The function is positive, so it maps into ${\mathbb{R}}^{+}$.)

(a) Yes. $\frac{n\log n}{n^{1.5}}=\frac{\log n}{n^{0.5}}\to 0$ by l’Hôpital: $\frac{1/(n\ln 2)}{0.5n^{-0.5}}=\frac{2}{\ln 2\cdot n^{0.5}}\to 0$ (here $\log ={\log }_2$). The limit is finite, so $n\log n\in O(n^{1.5})$.

(b) Yes. $2^{n+1}=2\cdot 2^n\le c{2}^n$ with $c=2$.

(c) No. $2^{2n}/2^n=2^n\to \infty$, so the quotient is unbounded. A change in the exponent is not a constant factor.

Question 2. Compute $46\cdot 73$ with Karatsuba’s method, using exactly three digit multiplications. Show each intermediate value and verify the result.

Solution to Question 2

Digits: $a=4$, $b=6$ (for 46); $c=7$, $d=3$ (for 73).

• $bd=6\cdot 3=18$
• $(a-b)(d-c)=(4-6)(3-7)=(-2)(-4)=8$
• $ac=4\cdot 7=28$

Combine: $xy=bd+10[bd+(a-b)(d-c)+ac]+100ac$:
$18+10(18+8+28)+100\cdot 28=18+540+2800=3358.$
Check: $46\cdot 73=46\cdot 70+46\cdot 3=3220+138=3358$ ✓.
Note that $a-b$ and $d-c$ are negative here; their product is still a single small multiplication.

Question 3. Solve $T(1)=1$, $T(n)=3T(n/2)$ for $n=2^k$ by telescoping, prove the result by induction, and express it as a power of $n$. Why does $T(n)\in O(n^2)$ hold but $n^2\notin O(T(n))$?

Solution to Question 3

Telescoping: $T(n)=3T(n/2)=3^{2}T(n/4)=\cdots =3^{j}T(n/2^j)$. With $j=k$: $T(n)=3^{k}T(1)=3^k$.

Induction on $k$, claim $T(2^k)=3^k$: IA: $T(1)=1=3^0$. IS: $T(2^{k+1})=3T(2^k)\stackrel{\text{IH}}{=}{3}^{k+1}$. $■$

As a power of $n$: $k={\log }_{2}n$, so $T(n)=3^{{\log }_{2}n}=n^{{\log }_{2}3}\approx n^{1.585}$, using $a^{{\log }_{b}n}=n^{{\log }_{b}a}$.

Comparison: $T(n)/n^2=n^{{\log }_{2}3-2}=n^{-0.415}\to 0$, so the quotient is bounded and $T\in O(n^2)$. Conversely $n^2/T(n)=n^{0.415}\to \infty$, so $n^2\notin O(T(n))$. Karatsuba is asymptotically strictly better than the school method.

Question 4. Suppose you split $n$-digit numbers in half but use the school identity $xy=BD+10^{n/2}(BC+AD)+10^{n}AC$ recursively, with four products of $n/2$-digit numbers. Set up and solve the recurrence. What does this show about Karatsuba’s trick?

Solution to Question 4

Recurrence: $T(1)=1$, $T(n)=4T(n/2)$. Telescoping: $T(n)=4^{k}T(1)=4^{{\log }_{2}n}=n^{{\log }_{2}4}=n^2$.
So divide and conquer alone gains nothing: it reproduces the school method’s $n^2$. The entire improvement comes from reducing the number of subproblems from 4 to 3. In general, $T(n)=aT(n/2)$ with $T(1)=1$ gives $n^{{\log }_{2}a}$. The exponent depends on the number of subproblems $a$, so saving even one subproblem changes the polynomial order.

Question 5. For Algorithm 1 of the Maximum Subarray Sum, compute the exact number of additions $A(n)={\sum }_{i=1}^n\frac{(n-i)(n-i+1)}{2}$ in closed form and confirm it lies between $\frac{1}{24}{n}^3$ and $\frac{2}{3}{n}^3$ (e.g. for $n=4$). Then state the number of additions of Algorithm 2 for $n=4$ and explain where the savings come from.

Solution to Question 5

Substitute $m=n-i$ (as $i$ runs from $1$ to $n$, $m$ runs from $n-1$ down to $0$):
$A(n)={\sum }_{m=0}^{n-1}\frac{m(m+1)}{2}=\frac{1}{2}({\sum }_{m=0}^{n-1}{m}^2+{\sum }_{m=0}^{n-1}m)=\frac{1}{2}(\frac{(n-1)n(2n-1)}{6}+\frac{(n-1)n}{2}).$
Factor out $\frac{(n-1)n}{12}$: $A(n)=\frac{(n-1)n}{12}((2n-1)+3)=\frac{(n-1)n(2n+2)}{12}=\frac{(n-1)n(n+1)}{6}=\frac{n^3-n}{6}.$

Check $n=4$: $A(4)=\frac{3\cdot 4\cdot 5}{6}=10$. Direct count: $i=1$: $0+1+2+3=6$; $i=2$: $0+1+2=3$; $i=3$: $0+1=1$; $i=4$: $0$. Total $10$ ✓.
Bounds: $\frac{1}{24}\cdot 64\approx 2.67\le 10\le \frac{2}{3}\cdot 64\approx 42.7$ ✓. Asymptotically $A(n)\approx n^3/6$, which indeed lies between $n^3/24$ and $2n^3/3$.

Algorithm 2, $n=4$: $\frac{4\cdot 3}{2}=6$ additions (rows: $3,2,1,0$). The saving: Algorithm 1 recomputes every prefix $a_i+\cdots +a_{j-1}$ from scratch for each $j$, costing $j-i$ additions. Algorithm 2 reuses $S_{i,j-1}$ and adds only $a_j$, costing 1 addition. Per start point $i$ the cost drops from $\Theta ((n-i{)}^2)$ to $\Theta (n-i)$, and overall from $\Theta (n^3)$ to $\Theta (n^2)$.