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.
I was riding the backseat of a car, a pal of mine with a large Sudoku book on the seat beside me. I glared over at him and remarked that I find Sudokus utterly boring and would feel that my time is wasted on any of them. He looked up at me, clearly demanding an explanation for that statement. I continued to explain that a computer program could solve a Sudoku with such ease that there is no need for humans to do it. He replied that something similar could be said about chess, but still it's an interesting game. And it was 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?