Problem Size
Problems in computer world are characterized with size, that is the number of data items in the problem.
A problem of size \(n\) can be considered as a sub problem of size \(n-1\) and one more data item. While a solution to the sub-problem of size \(n-1\) and the nth data item can be used to construct a solution to the original problem of size \(n\).
Partial Solution
For example, the summation of \(n\) data items is equal to the summation of first \(n-1\) data items plus the last, that is \(n\)-th data item.
$$sum_n=\sum_{j=1}^na_j$$
For problem of size \(i\), we have
$$sum_i=\sum_{j=1}^ia_j$$
Obviously,
$$sum_{i+1}=\sum_{j=1}^{i+1}a_j=\sum_{j=1}^ia_j+a_{i+1}=sum_i+a_{i+1}$$
A trivial case:
$$sum_{0}=\sum_{j=1}^{0}a_j=0$$
Another example: minimum element in an array. The minimum element of \(n\) data items is the smaller one of the minimum element of first \(n-1\) data tiems and the last data item.
$$min_n=\min_{j=1}^na_j=\min\{\min_{j=1}^{n-1}a_j,a_n\}=\min\{min_{n-1},a_n\}$$
A trivial case:
$$min_1=\min_{j=1}^{1}a_j=a_1$$
Examples:
3, right shift / left shift of an array
4, linear search
5, primality / all primes
6, \(\cos x\)
