# How can we calculate Big-O complexity in Functional & Reactive Programming

I started learning functional programming, I am trying to compare between different algorithms that are written in an imperative, functional , parallel programming and using Collections and Lambda expressions. In order to make my question clear and avoid sharing long algorithms that I am working on. I will take as an example the well-known modified Fibonacci algorithm (Euler Problem 2):

Here is the problem : http://projecteuler.net/problem=2

``````//Iterative way:

int result=2;
int first=1;
int second=2;
int i=2;

while (i < 4000000)
{
i = first + second;

if (i % 2 == 0)
{
result += i;
}

first = second;
second = i;
}

Console.WriteLine(result);

// Recursive functional way:
FibonacciTerms(1, 2).TakeWhile(x => (x <= 4000000) )
private static int SumEvenFibonarciTerms()
{
return FibonacciTerms(1, 2)
.TakeWhile(x => (x <= 4000000)).Where(x => x % 2 == 0)
.Sum();
}

//Asynchrounous way
let rec fib x = if x <= 2 then 1 else fib(x-1) + fib(x-2)

let fibs =
Async.Parallel [ for i in 0..40 -> async { return fib(i) } ]
|> Async.RunSynchronously
``````

How can I calculate the Big-O in algorithms that are written using Lamda expression (Complexity of functions like: filter, where, reduceleft, reducright, .. )

In the functional and Asynchrounous algo, the both are written in the same way ? Should we consider their complexity the same knowing that there is difference in the time of execution ?

• You need to know the performance of the underlying algorithms of the functions you're using. Dec 8, 2013 at 11:42
• For the recursive approach you need to know how a certain recurrence relation maps to the cost. See A Short Tutorial on Recurrence Relations for a longer explanation. Dec 8, 2013 at 11:46
• @MichaelT Alan Perlis, epigraphs on programming. But refers to lisp programmers (not to the language), presumably implying these programmers don't care about performance. At least in strict functional languages (such as virtually every Lisp), deriving time bounds is no harder than in imperative languages.
– user7043
Dec 8, 2013 at 12:20
• You can check this post discussing functional programming solution mentioning that's heavy : stackoverflow.com/questions/4101924/… Dec 8, 2013 at 16:48