@DanielFischer The recurrence relation should describe the time that is required so that an algorithm runs. So isn't $\alpha$ the number of subproblems into which the initial problem is divided? Or am I wrong? If so, then $\aplha$ is an integer, right?
@evinda If the recurrence is guaranteed to come from the divide-and-conquer routine, then $\alpha$ is an integer. If it's just an abstract recurrence, who knows?
If SE, decided mention of the number "one" was forbidden, they could ban people accordingly. It might not be conducive to the site's health, but they'd be within their rights to do so.
You can, under certain circumstances. But the police have certain powers as law enforcement officials ordinary citizens do not. To successfully sue, you have to show they exceeded or unlawfully exercised said authority, which is not easy to do.
@DanielFischer I thought that it would always be the number of subproblems. Now I saw that the exercise asks for the greatest integer value for which A' is asymptotically faster than A. So is that what I have done right?
@evinda Probably. There's a small possibility that "faster" means "strictly faster or equally fast". To be on the safe side, you could add something along the lines of "assuming that 'faster' means 'strictly faster' here" if you're unsure.
@Mike Should I make a digression and peek at Milnor's Topology from a differentiable viewpoint that Hatcher refers to? I am not sure if I have the background.
@DanielFischer Oh okay. Then for $g_{y}(1,0)$ would it follow that $g_{y}(1,0) = \lim\limits_{y \rightarrow 0}\frac{g(1,y - g(1,0))}{y} = \lim\limits_{y \rightarrow 0}\frac{y^{2}+1}{y}$?
What does he refer to it about? It's something of an entirely different flavor. Assuredly you have the background but if you just want to hear about one thing I can say a word.
@evinda Not really. It may be good to mention that a smaller $\alpha$ cannot produce a slower algorithm than a larger one, and hence $\alpha \leqslant 16$ need not be explicitly considered.
I told you about it, but maybe you want to read the details. The degree of a smooth map between closed n-manifolds is the (signed) number of points in the image of a "generic" point in the codomain.
The sign comes from counting things positively if they're locally orientation-preserving at that point, and negatively if they're locally orientation-reversing at that point.
@MikeMiller Probably it's just an easy consequence of the local degree formula, but I don't quite see how that interacts with the homology definition, which presumably I told you before.
@ABeautifulMind If anyone thinks Milnor's definition is a good definition, they are absolutely, impossibly wrong. This is not even a statement of opinion, like you say yours on Munkres is. It is a statement of fact.
@DanielFischer So it is not possible to write a general partial derivative since the function is not differentiable at each point, one has to check specific points?
@MikeMiller Well, homology groups of arbitrary manifold is obviously not $\Bbb Z$. So I am not sure how degree of maps from manifolds to manifolds can be discussed in terms of homology.
@JohnJack Well, we have a closed formula for $g$ on the open set $\{(x,y) : x \neq 0 \land y \neq 0\}$, we get a closed formula for the partial derivatives there, and then need only consider the points where $x = 0$ or $y = 0$ specially.
Proof of equivalence for S^n: a 'generic point' $q$ for the map $f$ is one such that, restricted to a suitably small neighborhood $U$ of $q$, $V = f^{-1}(U)$ is a disjoint union of small open sets, each of which maps diffeomorphically onto $U$. (aka, it's a covering map 'near' $q$.) Consider the map $f': S^n /V^c \to S^n$. The domain is a wedge product of a bunch of spheres, and on each sphere, the map is a diffeomorphism. (Homeomorphism, if you like.)
The degree of the whole map $f$ is just the sum of the degrees of each of these induced maps on the wedge product of spheres; and each of those is +1 or -1 depending on whether it's orientation-preserving or reversing.
There are a few details missing in that (why is the degree of the whole map the sum of the degrees? I guess I can explain that if you insist; why does there exist a generic point?), but the above is why it's true.
Well, I actually used it while proving that a polynomial of degree $n$ from $\Bbb C \to \Bbb C$ induces a degree $n$ map $S^2 \to S^2$ given by compactifying.
@DanielFischer Ok.. at which point could I mention that that a smaller $\alpha$ cannot produce a slower algorithm than a larger one, and hence $\alpha \leqslant 16$ need not be explicitly considered ? After having found the largest value for $\alpha$?
@ᴇʏᴇs Each time I talk about my problems in the Eng room, some folks there tell me to stop self-pitying. That makes me upset. I just wanted to say some things so that I feel better. I think I won't talk to them anymore.
Replacing $x$ by $x^2$ and $y$ by $y^2$ all reduces to
$$2\le|x+y|$$
that is true with $x\ge1$ and $y\ge1$.
