Is the computational complexity of this function O(2^n) or O(n)

Question

I want to make a function that creates an infinite list that takes two numbers and an operator as input so it can generate arithmetic and geometric sequences.

infiniteList:: (Floating a)=>a->(a->a->a)->a->[a]
infiniteList start operation changeby = 
  start:[(operation x changeby)| x<-(infiniteList start operation changeby)]

the code compiles and works properly: infiniteList 1 (*) 2 generates a list starting from 1 and subsequent numbers are double its predecessor.

Now I'm having trouble figuring out the computational complexity "to calculate the nth element of the list". Technically it is doing one operation to figure out each element of the list. However, if you were after the (2^k +1) term, I would have to wait for the computer to finish calculating 2^(k+1) elements first.

I hope I'm explaining this properly, so basically I think the program produces the elments in 2^k batches where k is an integer, so you could potentially be waiting for ( 2^(k+1)-2^k) time to calculate the (2^k +1)th integer. So what is the computational complexity "to calculate the nth element of the list"?

Answer 1

The run time depends a lot on how GHC decides to evaluate it.

To simplify things, consider this version of the function:

inf a f = a : [ f x | x <- inf a f ]

If GHC performed common sub-expression elimination on int a f, it could decide to evaluate it as if it had been written:

inf a f = let r = a : [ f x | x <- r ]
          in r

and this runs in linear time.

Answer 2

A key tool is the following rule:

When analyzing the performance (not the totality) of a binding, you are allowed to assume, when analyzing its right-hand-side, that the binding itself has been fully evaluated.

You are defining infiniteList, so you are allowed to assume that in the RHS, the infiniteList binding has been fully evaluated. That, unfortunately, isn't useful, because infiniteList is just a function, and fully evaluating it just gives you the function!

But you can use this reasoning tool to figure out a fix: you have to bind the right thing.

infiniteList :: a -> (a -> a -> a) -> a -> [a]
infiniteList start operation changeby =
  let result =
    start : [operation x changeby | x <- result]
  in result

Now you have a useful binding, result, which you can assume is fully evaluated! In the RHS, you now have, essentially,

start : map (\x -> operation x changeby) result

which is clearly O(n).

Indeed with the first definition,

> infiniteList 1 (*) 2 !! 10000

takes longer than I wish to wait, but with the modified definition, it takes a mere 0.04 seconds even in GHCi.

Answer 3

One strategy that sometimes helps with recursion is to expand it out a few times to get a better idea of what's going on. Let's try that:

infiniteList start operation changeby = 
start:[(operation x changeby) | x <-
       start:[(operation x changeby) | x <-
              start:[(operation x changeby) | x <-
                     start:[(operation x changeby) | x <-
                            start:[(operation x changeby) | x <- (infiniteList start operation changeby)]]]]]

We can see the first element in the list is going to be start as expected. Then the second element will be start from the first recursive call passed through operation x changeby. What will the third item be? Well it'll be the second item of the first recursive call, so it'll be start passed through two calls of operation x changeby. Now the pattern emerges! In general, the nth item of infiniteList will be start with operation x changeby called on it n-1 times. This is rather unfortunate because ,as any student of computer science knows, 1 + 2 + ... + n - 1 = n(n-1)/2 = O(n^2).

There is, of course, a much more efficient way to write this function. Instead of applying operation x changeby to start n-1 times to get the nth item, why don't we just apply it once to the previous item? This will give us an O(n) solution. For example, we can use unfoldr from Data.List:

import Data.List (unfoldr)

infiniteList start operation changeby =
    unfoldr (\x -> Just (x, operation x changeby)) start

Answer 4

Just do some math, assume calculate nth item requires T(n) calculations, as

[(operation x changeby)| x<-(infiniteList start operation changeby)]

suggests, we need to know sub problem T(n-1), and the full list comprehension have n-1 operations, and then concat star:... operation is efficient, and have 1 calculation, so

T(n) = T(n-1) + (n - 1) + 1 = T(n-1) + n -> O(n^2)

---

Actually, you can "feel" the time complexity just by running some examples. Let f n = (infiniteList 0 (+) 1) !! n, then run f 10, f 100, f 1000, f 10000, you can see the difference.

Usually, when n=1000 runs in no time, n=10000 run some time like 1 or 2 seconds, and n=100000 run forever, it is usually O(n^2).

---

BTW, there is an O(n) approach:

infi :: a -> (a -> a -> a) -> a -> [a]
infi x f s = x : infi (f x s) f s

You can do some math and run some examples to feel the difference.

Answer 5

I'm not sure where you are getting the "batches" idea from. Below is a transcript of the first few elements of the list. From that, I think you should be able to figure out the complexity.

What's the first element of the list? It is start, because infiniteList is defined as start:[something], and the first element of any list of that form is start.

What is the second element of the list? We certainly need to consult the [something] portion of the list above. The first element of that sublist is operation x changeby where x is the first element of infiniteList. We decided already that the first element is start, so the second element is operation start changeby, which is exactly what we wanted. What do we have to compute to get the second element? Just the first, plus the operation.

What is the third element of the list? It's the second element of [something], which is operation x changeby where x is the second element of infiniteList. Fortunately, we just calculated what that is... What do we have to compute to get the third element? Just the first and second, plus the operation.

Although it doesn't directly answer the question, you should ask yourself what complexity you expect the function to have. How much work needs to be done to get the nth element? It's possible that your implementation in code is worse, but it might help you think about your code differently.