7

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 ?

Improve this question
4
  • 1
    You need to know the performance of the underlying algorithms of the functions you're using. – CodesInChaos Dec 8 '13 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. – CodesInChaos Dec 8 '13 at 11:46
  • 1
    @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 '13 at 12:20
  • You can check this post discussing functional programming solution mentioning that's heavy : stackoverflow.com/questions/4101924/… – user3047512 Dec 8 '13 at 16:48
4

Your programming language paradigm may help you to write code in less line or to express yourself in an easier. It won't change complexity of your program. The questions remaining are the same:

  • What's the worst case ?
  • How much "unit" operations are require to perform your algorithm ?

This means that you have to mostly understand how your data structures behave and your code by itself.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.