Induction for recursive function In of my computer science classes, there is the following exam question:
Let an algorithm solve a problem of size $n$ by dividing it into the size $n \over 2$ in $n \over 2$ steps (division without remainder) and solve this problem recursively with the same strategy. A problem of size $1$ is solved in one step. Therefore, we have the function
$$f: \Bbb N \rightarrow \Bbb N$$
$$f(n) = {n \over 2 } + f\left({n \over 2}\right)$$
for $n > 1$ and $1$ for $n = 1$. One has to prove that $f(n) \in O(n)$.
I don't quite see how to perform the induction step here.
$$f(n+1) = {(n+1) \over 2} + f\left({n+1 \over 2}\right).$$
Now, the function has an input $n+1 \over 2$, which is a natural number by premise. But how to apply $f(n) \le n$ then?
 A: No, $n+1$ is not a good candidate, as $(n+1)/2$ cannot be an integer. You should consider a geometric progression instead, giving
$$f(2n)=n+f(n)=n+\frac n2+f(\frac n2)$$
$$f(4n)=2n+f(2n)=2n+n+\frac n2+f(\frac n2)$$
$$...$$
or, going the other way,
$$f(n)=\frac n2+\frac n4+\frac n8+f(\frac n8)=\frac n2+\frac n4+\frac n8+\frac n{16}+f(\frac n{16})=\cdots$$
A: Here, one has to solve one problem of size $n/2$ and add the cost of the division operation (here $n/2$). If $n = 2^p$ is a power of two, one has
\begin{equation}
f(2^p) = f(2^{p-1}) + 2^{p-1} \, ,
\end{equation}
with the condition $f(2^0) = 1$. Dividing by $2^p$, an affine recursion is obtained:
\begin{equation}
\frac{f(2^p)}{2^p} = \frac{1}{2}\frac{f(2^{p-1})}{2^{p-1}} + \frac{1}{2} \, ,
\end{equation}
with $p$th term
\begin{equation}
\frac{f(2^p)}{2^p} = 1 \, .
\end{equation}
Therefore, for powers of two, one has exactly $f(n) = n$ . If $n$ is not a power of two, there exists $p$ such that $2^{p-1} < n < 2^{p}$. Since $f$ is increasing, one has $2^{p-1} < f(n) < 2^{p}$. Finally, $\frac{n}{2} < f(n) < 2n$ , which ends the proof: $f(n) = \underset{n\rightarrow\infty}{O} (n)$ .
Notes:
(a) We can say more. The function $f(n)$ is not only a $O(n)$, since $n$ is also a $O(f(n))$. This is classically denoted by $f(n) = \underset{n\rightarrow\infty}\Theta(n)$.
(b) If we had to solve two problems of size $n/2$ and add the cost of the division operation, we would deal with a case similar to the merge sort, and would obtain $f(n) = \underset{n\rightarrow\infty}{\Theta} ( n\log n )$ .
