3: First Order Recurrence Relations

Check out the project description here

First Order what?
First order recurrence is a type of a recursive equation that can be . The following equations have first order recurrence relations:

• The coefficients are constants and only to the first power
• The nth term depends only on term ( n - 1 )
• General Form: S(n) = cS( n - 1 ) + g(n)

Here is the equation to convert first order recursive equations into linear equations

• S(n) = C^n-1S(1) + ⁿΣ_i=2 [ C^n-i * g(n) ]

Quick example

• Original: S(n) = 2*S( n - 1 ) + 3
• Becomes: S(n) = 2^n-1 * S(1) + ⁿΣ_i=2 [ 2^n-i * 3 ]

Imagine inputing 5,000 for n. The second equation would have a significantly smaller big-O complexity

The Code
Due to the fact that my professor usually gives us read-in-files contain similar formats I decided to make a master parsing class that you can look at on github if you want.

• The code doesn't contain anything fancy.
• I love ruby's exponent operator **
• I love ruby's for loops