Ich habe letzte Woche versucht, für einige Studenten das Master Theorem zu beweisen. Das ist geringfügig daneben gegangen, deswegen habe ich eine korrigierte Version des Beweises erstellt. Ich frage mich nun aber schon, wie allgemein man das eigentlich machen sollte. Grundsätzlich könnte man sich für eine Laufzeitfunktion $T:\mathbb N\to\mathbb N$ ja Rekurrenzgleichungen der Form $T = \alpha \circ T \circ \beta$ ansehen, wobei in meinem Fall $\beta(n)=n/b$ und $\alpha(n)=a\cdot n + f(n)$ ist. Ich habe leider keine Zeit, mir dazu mehr Gedanken zu machen.

**then**, that I realized

**why**Sudoku is so horribly boring, and chess is not. It was the fact that I could code a Sudoku solver and solve the Sudoku he was puzzling about, and I would be able to do it faster than it would take him to solve the entire thing by hand. This does not apply to chess, evidently. Of course, I confidently explained this to him.

*»Prove it.«*, he said. So I did. Do you want to know more?