91Ó°ÊÓ

A function of theoretical importance in the study of algorithms is the Ackermann's function, named after the German mathematician and logician Wilhelm Ackermann (1896-1962). It is defined recursively as follows, where \(m, n \in \mathbf{W}:\) $$A(m, n)=\left\\{\begin{array}{ll}n+1 & \text { if } m=0 \\\A(m-1,1) & \text { if } n=0 \\\A(m-1, A(m, n-1)) & \text { otherwise }\end{array}\right.$$ Compute each. $$A(2,2)$$

Let \(a, b, n \in \mathbb{N}, b \geq 2, c, d \in \mathbb{R}^{+}, f(1)=d,\) and \(n\) is a power of \(b .\) Let \(f\) be a non decreasing function such that \(f(n)=a f(n / b)+c n^{2} .\) Prove each. If \(a=b^{2},\) then \(f(n)=n^{2} d+c n^{2} \log _{b} n\)

Let \(a, b, n \in \mathbb{N}, b \geq 2, c, d \in \mathbb{R}^{+}, f(1)=d,\) and \(n\) is a power of \(b .\) Let \(f\) be a non decreasing function such that \(f(n)=a f(n / b)+c n^{2} .\) Prove each. If \(a \neq b^{2},\) then \(f(n)=A n^{2}+B n^{\log _{b} a},\) where \(A=\frac{b^{2} c}{b^{2}-a}\) and \(B=d+\frac{b^{2} c}{a-b^{2}}\)

Prove each for \(n \geq 0\) $$A(1, n)=n+2$$

Let \(a, b, n \in \mathbb{N}, b \geq 2, c, d \in \mathbb{R}^{+}, f(1)=d,\) and \(n\) is a power of \(b .\) Let \(f\) be a non decreasing function such that \(f(n)=a f(n / b)+c n^{2} .\) Prove each. $$f(n)=\left\\{\begin{array}{ll} \mathrm{O}\left(n^{2}\right) & \text { if } a < b^{2} \\ \mathrm{O}\left(n^{2} \lg n\right) & \text { if } a=b^{2} \\ O\left(n^{\log _{b} a}\right) & \text { if } a > b^{2} \end{array}\right.$$

Prove each for \(n \geq 0\) $$A(2, n)=2 n+3$$