Come possiamo calcolare la complessità del Big-O nella programmazione funzionale e reattiva

Ho iniziato a imparare la programmazione funzionale, sto cercando di confrontare diversi algoritmi scritti in una programmazione imperativa, funzionale, parallela e utilizzando le espressioni Collections e Lambda. Per chiarire la mia domanda ed evitare di condividere i lunghi algoritmi su cui sto lavorando. Prenderò come esempio il noto algoritmo di Fibonacci modificato (Eulero Problema 2):

Ecco il problema: link

//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

Come posso calcolare il Big-O in algoritmi scritti usando l'espressione Lamda (complessità di funzioni come: filtro, dove, reduceleft, reducright, ..)

Nell'algo funzionale e asincrona, entrambi sono scritti nello stesso modo? Dovremmo considerare la loro complessità lo stesso sapendo che c'è una differenza nel tempo di esecuzione?