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

i want make function creates infinite list takes 2 numbers , operator input can generate arithmetic , 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 , works properly: infinitelist 1 (*) 2 generates list starting 1 , subsequent numbers double predecessor.

now i'm having trouble figuring out computational complexity "to calculate nth element of list". technically doing 1 operation figure out each element of list. however, if after (2^k +1) term, have wait computer finish calculating 2^(k+1) elements first.

i hope i'm explaining properly, think program produces elments in 2^k batches k integer, potentially waiting ( 2^(k+1)-2^k) time calculate (2^k +1)th integer. computational complexity "to calculate nth element of list"?

a key tool following rule:

when analyzing performance (not totality) of binding, allowed assume, when analyzing right-hand-side, binding has been evaluated.

you defining infinitelist, allowed assume in rhs, infinitelist binding has been evaluated. that, unfortunately, isn't useful, because infinitelist function, , evaluating gives function!

but can use reasoning tool figure out fix: have bind right thing.

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

now have useful binding, result, can assume evaluated! in rhs, have, essentially,

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

which o(n).

indeed first definition,

> infinitelist 1 (*) 2 !! 10000 

takes longer wish wait, modified definition, takes mere 0.04 seconds in ghci.