$\newcommand{\vct}[1]{\mathbf{#1}}$ $\newcommand{\mtx}[1]{\mathbf{#1}}$ $\newcommand{\e}{\varepsilon}$ $\newcommand{\norm}[1]{\|#1\|}$ $\newcommand{\minimize}{\text{minimize}\quad}$ $\newcommand{\maximize}{\text{maximize}\quad}$ $\newcommand{\subjto}{\quad\text{subject to}\quad}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\trans}{T}$ $\newcommand{\ip}[2]{\langle {#1}, {#2} \rangle}$ $\newcommand{\zerovct}{\vct{0}}$ $\newcommand{\diff}[1]{\mathrm{d}{#1}}$
(a) We apply the bound inductively,
\begin{equation*} \norm{\vct{x}_k-\vct{x}^*}\leq r\cdot \norm{\vct{x}_{k-1}-\vct{x}^*}\leq r \cdot (r \cdot \norm{\vct{x}_{k-2}-\vct{x}^*})\leq \cdots \leq r^k\cdot \norm{\vct{x}_{0}-\vct{x}^*}. \end{equation*}(b) Let $\e>0$. We are guaranteed to have an error bounded by $\e$ if $r^N\cdot M<\e$, by Part (a). Taking logarithms of this inequality,
\begin{equation*} N\ln(r) + \ln(M)\leq \ln(\e). \end{equation*}Negating this, we get
\begin{equation*} -N\ln(r) - \ln(M)=N\ln(1/r) - \ln(M)\geq \ln(1/\e). \end{equation*}Dividing by $\ln(1/r)$ gives
\begin{equation*} N \geq \frac{1}{\ln(1/r)} \left(\ln(1/\e)+\ln(M)\right) > \frac{r}{1-r}\left(\ln(M)+\ln(1/\e)\right), \end{equation*}where we used the inequality $\ln(1/r)<1/r-1 = (1-r)/r$.
(c) For quadratic convergence, the bound is derived in exactly the same way as for linear convergence. To determine the number of steps, we start with the bound
\begin{equation*} C^N\cdot M^{2^N}\leq \e. \end{equation*}Taking logarithms and negating,
\begin{equation*} N\ln(1/C)-2^N\ln(M) \geq \ln(1/\e). \end{equation*}Taking logarithms again, we get
\begin{equation*} N\cdot \left(\frac{\log_2(N)}{N}+\log_2(\ln(1/c)-\ln(M))\right) \geq \log_2 (\ln(1/\e)), \end{equation*}so that if
\begin{equation*} N> C'\cdot \ln\ln(1/\e) \end{equation*}for a constant $C'$, we are guaranteed an error below $\e$.
We first compute the derivatives,
\begin{align*} f(x) &= \sqrt{x^2+1}\\ f'(x) &= \frac{x}{\sqrt{x^2+1}}\\ f''(x) &= \frac{1}{(x^2+1)^{3/2}}. \end{align*}Note that the second derivative is always positive. Newton's method then has the following form
\begin{equation*} x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)} = x_k - x_k(1+x_k^2) = -x_k^3. \end{equation*}For $|x_0|<1$ this clearly converges to $0$, while for $x_0>1$ this diverges. For $|x_0|=1$ the sequence alternates between $1$ and $-1$.
We first have to think about what it means to be a steepest descent direction with respect to a norm. If we look for a vector $\vct{p}$ with $\norm{\vct{p}}_\infty=1$ such that $\ip{\vct{p}}{\nabla f(\vct{x})}$ is minimal. Set $\vct{v}=\nabla f(\vct{x})$, to ease notation. Since $\norm{\vct{p}}_\infty = 1$ is the same as saying that $\max_{1\leq i\leq n} |p_i| = 1$, this amounts to solving the minimization problem
\begin{align*} \minimize& \ip{\vct{p}}{\vct{v}}\\ \subjto & -1 \leq p_i \leq 1, \quad 1\leq i\leq n. \end{align*}Suppose that a minimizer is found and the minimum has the form
\begin{equation*} \sum_{i=1}^d p_i v_i. \end{equation*}If $p_iv_i>0$, then we can decrease the objective function further by changing the sign of $p_i$, and then even further by setting $p_i=-1$ if $\mathrm{sign} \ v_i=1$ and $p_i=1$ otherwise. Therefore, the optimizer has the form
\begin{equation*} p_i = -\mathrm{sign} \ \nabla f(\vct{x})_i \end{equation*}for $1\leq i\leq n$.