Algorithms/Recursion Analysis

Notes

This page contains notes on algorithmic analysis of recursive functions.

Goodrich Chapter 4

English Ruler Example: Setup

An English ruler is a ruler in which each major unit has major tick marks, and minor units have minor tick marks occurring at successive halves. Between marks for whole inches, there are minor ticks at 1/2 inch intervals; between the 1/2 inch intervals, minor ticks at 1/4 inch intervals; etc.

To draw in ascii:

---- 0
-
--
-
---
-
--
-
---- 1
-
--
-
---
-
--
-
---- 2

Implementation looks like this:

function draw line(tick length, tick label):
    line = '-' (tick length times)
    if tick label:
        line += ' ' + tick label
    print line

function draw interval(center length):
    if center length > 0:
        draw interval(center length - 1) /* recursively draw top ticks */
        draw line(center length) /* draw center tick */
        draw interval(center length +1) /* recursively draw bottom ticks */

function draw ruler(number of inches, major length):
    draw line(major llength, '0') /* 0 inch line */
    for j in range(1, 1+inches+1):
        draw interval(major length - 1) /* draw interior ticks for inch */
        draw line(major length, str(j)) /* draw inch j line and label */

in general, an interval with tick length L >= 1 is composed of the following:

• an interval with a central tick length L-1
• a single tick of length L
• an interval with a central tick length L-1

English Ruler Example: Analysis

Fundamental question we want to know, in analyzing the above method, is how many lines of output it will produce by a call to draw_interval(c), where c is a center length.

Each line of output is based upon a call to the draw line utility, and each recursive call to draw interval makes exactly one call to draw line, unless 0.

Proposition: For $c\geq 0$, a call to draw_interval(c) results in precisely $2^{c}-1$ lines of output.

Justification: (Proof by induction) We note first the base case is c = 0, which generates no output, and $2^{0}-1=1-1=0$. This is the base of the claim.

Next, we can see that the number of lines printed by draw_interval(c) is one more than twice the number generated by a call to draw_interval(c-1), as once center line is pinted between two such recursive calls. By induction, the numberof lines must be 1 + 2 * prior number, which is:

$1+2(2^{c-1}-1)=1+2^{c}-2=2^{c}-1$

Therefore it is proven.

This relates to the Algorithms/Recurrence Relation concept.