Arda

Worth mentioning where this stops being a homework curiosity, because it motivates the whole thing: this is exactly why algorithm speed is discussed in these terms.

An algorithm whose work grows like x squared is slow but usable at large sizes. One whose work grows like 2 to the x is fine on small inputs and impossible not much later — not slow, impossible, as in longer than the age of the universe for inputs that fit on a page.

The crossover he is being asked about is the reason that distinction is the first thing anyone learns about algorithms.

Practical note from the other side: in real hardware and software design, the continuous model is usually the least wrong part of the analysis.

The cost function itself is an idealisation — it ignores layout, routing, cache behaviour, manufacturing variation, and everything else that decides the actual answer. Worrying about whether the optimum is at 6 or 7 stages when the model has a twenty percent error is misplaced precision.

So the honest engineering position is: use the calculus to find the neighbourhood, check the two or three candidates properly, and then measure. The mathematics gets you to the right street; it does not pick the house.

One thing worth knowing early, because it explains a detail that confuses people later: the series above only works with the angle in radians, not degrees.

That is not a convention chosen to annoy students. Radians are the measure in which the series comes out that clean — in degrees you would need an ugly conversion factor scattered through every term. It is the first example you will meet of a unit being chosen because it makes the mathematics simple rather than because it is convenient for humans.

One with a very short statement: 8 and 9 are the only pair of consecutive perfect powers.

That is, among all numbers that are a whole number raised to a whole power greater than one — 4, 8, 9, 16, 25, 27, 32 and so on — you will never find two that differ by exactly one, other than 8 and 9.

It was conjectured in the middle of the nineteenth century and only proved at the start of this one. So for about a hundred and fifty years everyone was confident there was exactly one exception without being able to rule out a second hiding somewhere enormous.

That gap between "obviously true" and "proved" is its own kind of interesting.

The clearest way to see what goes wrong with the nearest-city heuristic is that it is forced to pay for its own convenience at the end.

At every step it takes the cheapest available hop. That is locally sensible and it leaves behind a set of cities that are far from each other and far from where you now are — precisely the ones it kept skipping because something closer was available. The final legs of the tour are then enormous, and they cost more than everything the greedy choices saved.

You can construct arrangements where this is arbitrarily bad, and the constructions are not contrived: a line of closely spaced cities with one outlier does it. The greedy route runs happily down the line and then has to cross the whole map twice.

The general principle is that the cost of a decision in this problem is not visible when the decision is made. Any method that commits early without accounting for what it leaves behind can be defeated.

From my end of the subject: the unsolvability results.

There is no general algorithm that decides whether two elements of an arbitrary group are equal. There is no general algorithm that decides whether a program halts. There is no general algorithm that solves arbitrary polynomial equations in integers.

Each of these was posed as a challenge — go and find the procedure — and each was answered with a proof that no procedure exists. That is a much colder answer than "nobody has found it yet", because it forecloses the search entirely.

The consolation is that all three led directly to understanding why certain problems are hard, which turned out to be more useful than any of the procedures would have been. Impossibility results are how a field learns where its boundaries are.

Worth adding that "unsolvable" often means "solvable, in terms of functions you have not been introduced to".

A great many equations that appear intractable have solutions in terms of named special functions — Bessel, Airy, elliptic and their relatives. Those functions exist precisely because somebody needed them for an important equation, computed them thoroughly, tabulated them and gave them a name.

Which reframes what an elementary function is. Sine is not fundamentally simpler than a Bessel function; it is older, more useful and taught earlier. The class of closed-form solutions is a historical accident about which functions became familiar, not a mathematical boundary.