2.4 Mathematical Analysis of Recursive Algorithms

Question 1

play an important role
not only in analysis of algorithms but also in some areas of applied mathematics.
They are usually studied in detail in courses on discrete mathematics or discrete
structures; a very brief tutorial on them is provided in Appendix B. Our goal now
is to solve the recurrence relation M(n) = M(n − 1) + 1, i.e., to find an explicit
formula for M(n) in terms of n only.

Answer 1

recurrence relations

Question 2

The method’s idea (and the reason for the name) is immediately
clear from the way it applies to solving our particular recurrence:
M(n) = M(n − 1) + 1
substitute M(n − 1) = M(n − 2) + 1
= [M(n − 2) + 1] + 1 = M(n − 2) + 2
substitute M(n − 2) = M(n − 3) + 1
= [M(n − 3) + 1] + 2 = M(n − 3) + 3.
After inspecting the first three lines, we see an emerging pattern, which makes it
possible to predict not only the next line (what would it be?) but also a general
formula for the pattern: M(n) = M(n − i) + i. Strictly speaking, the correctness of
this formula should be proved by mathematical induction, but it is easier to get to
the solution as follows and then verify its correctness.
What remains to be done is to take advantage of the initial condition given.
Since it is specified for n = 0, we have to substitute i = n in the pattern’s formula
to get the ultimate result of our backward substitutions:

Answer 2

M(n) = M(n-1)=… =M(n-i)=..M(n-n) + n =n

Question 3

General planning for analysis of time efficiency of recursive algorithms:

Answer 3

1. Decide on a parameter (or parameters) indicating an input’s size.
2. Identify the algorithm’s basic operation
3. Check whether the number of times the basic operation is executed can vary
   on different inputs of the same size; if it can, the worst-case, average-case, and
   best-case efficiencies must be investigated separately.
4. Set up a recurrence relation, with an appropriate initial condition, for the
   number of times the basic operation is executed.
5. Solve the recurrence or, at least, ascertain the order of growth of its solution.

Question 4

theorem that claims that under very broad assumptions the order of growth observed for
n = 2k gives a correct answer about the order of growth for all values of n. (Alternatively, after getting a solution for powers of 2, we can sometimes fine-tune this
solution to get a formula valid for an arbitrary n.)

Answer 4

smoothness rule