Computer Science 789 Online Algorithms

Hint 4 for the Pascal Recursion Problem

Prove that the number of recursive calls is not more than 2 lg(n). Use strong induction.

We can assume n > 0 by the input condition.

The other three cases are n=1, n > 1 even, and n > 1 odd.

If n=1, the result is trivial, since there is no recursion, and lg(1) = 0.

Back to Course Page

Back to Assignment Page

Back to Assignment 1