1

I have following function which has exponential complexity:

c :: Integer -> Integer
c n 
   | n <= 4 = n + 10
   | otherwise = c (n-1) + 2 * (c (n-4))

I'm struggling to make the complexity of this function to linear.

c x shoud terminate even if 1000 < x < 100000

Kert Kukk
  • 666
  • 1
  • 10
  • 20
  • 2
    Take a look at the [canonical Fibonacci implementation](https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zipWith_implementation). – n. m. could be an AI Jan 12 '17 at 07:33
  • You can just tabulate the values for that function starting from `0` and replace the recursive calls with lookups over this table. Using a simple list this becomes O(n^2). As suggested by n.m. this can then evolve in a way that avoids the O(n) lookups and achieve O(n) total complexity. – Bakuriu Jan 12 '17 at 07:51
  • 1
    This is a semi-duplicate of https://stackoverflow.com/questions/3208258/memoization-in-haskell. – Zeta Jan 12 '17 at 10:21

1 Answers1

5

There are at least two ways to solve this problem linearly in time.

Using intermediate memory

c1 :: Integer -> Integer
c1 n 
  | n <= 4 = n + 10
  | otherwise = go n (map c1 [4,3,2,1])
  where
    go 4 (a:_) = a 
    go n [a,b,c,d] = go (n-1) [a + 2*d, a, b, c]

Here we use four intermediate registers and shift them while going through the cycle. We could use tuple (a, b, c, d) instead of a list, but it is more handy to start with mapping here.

This solution is constant in space and linear in time.

Memoization (codata generation)

c2 :: Integer -> Integer
c2 n
  | n <= 4 = n + 10
  | otherwise = results !! fromInteger (n - 1)
  where
    results = [11..14] ++ zipWith f (drop 3 results) results 
    f a b = a + 2*b

Here we use the laziness of Haskell (normal evaluation strategy + memoization). The infinite list results generates values one-by-one on demand. It is used as data by c2 function which just requests the generator for n-th number, and in self-definition. At the same time this data does not exist until it is needed. Such sort of data is called codata and it is rather common in Haskell.

This solution is linear in space and time.

Both solutions handle negative numbers and large positive numbers.

samsergey
  • 228
  • 1
  • 8
  • Another approach is to express the recurrence in terms of matrix multiplication. That is, given a column vector of four successive elements of the sequence, you can multiply them on the left by a fixed matrix to get the next four elements of the sequence. `m * m * m * ... * v`. But this is just `m ^ k * v`, and using exponentiation by squaring (`stimesMonoid`), this calculation is much more efficient, in practice, than `c1`. – dfeuer Jan 12 '17 at 21:55
  • 1
    @dfeuer, That's indeed excellent mathematical approach for recurrent formulas, both elegant and practical. In general non-numeric (or nonlinear ) cases iterative cycles or memorization are still useful. – samsergey Jan 13 '17 at 05:04