CODEWITHSUNDEEP
algorithmrecursionocamlcomplexity-theory
SoftTimur
SoftTimur

Reputation: 5510

Complexity of a recursive function with a loop

I have a recursive function working on a list, the function contains a loop where itself is called, and ends up with another function g. Its structure is similar as follows, to simplify the issue, we can assume that l is always a list without duplicate elements.

let rec f l = function
  | [] -> g ()
  | _ ->
      List.fold_left
        (fun acc x ->
           let lr = List.filter (fun a -> (a <> x)) l in
           acc + (f lr))
        1 l

I am not sure how to express the complexity of this function, with List.length l and the complexity of g.

I think it is proportional to the complexity of g and the factorial of List.length l, could anyone confirm?

Upvotes: 2

Views: 1582

Answers (2)

Victor Nicollet
Victor Nicollet

Reputation: 24577

Since you assume that the list l does not contain any duplicates, what this function does is compute all sublists that have one less element than the original list and call itself recursively on all of them. So, the number of times g is called when starting with a list of size n is g?(n) = n · g?(n-1) = n!

Now, let's consider everything else the function has to do. The amount of work at each step of the recursion includes :

  • For each element in the original list, constructing a new list of one less element. This is a total amount of work equal to n2
  • Once the result of the recursive call is known, add it to an accumulator. This is a total amount of work equal to n (this part can be ignored, since the filter is more costly).

So, since we know how many times each recursive step will be called (based on our previous analysis), the total amount of non-g related work is: t?(n) = n2 + n (n-1)2 + n (n-1) (n-2)2 + ... + n!

This formula looks like a pain, but in fact t?(n) / n! has a finite non-zero limit as n increases (it is the sum of the k+1 / k! with 0 < k < n) and so t?(n) = Θ(n!).

Upvotes: 1

Gene
Gene

Reputation: 46960

Okay. I don't mean to seem mustrustful. This really does look like a functional programming homework because it's not very practical code.

Let F(n) be the number of comparisons plus the number of additions for an input of length n. And let G be the run time of g. Since g doesn't take any operands, G is constant. We are just counting the number of times its called.

The fold will execute its function n times. Each execution will call filter to do n comparisons and remove exactly one element from its input each time, then recursively call f on this shortened list and do one addition. So the total cost is

F(n) = n * (n + F(n - 1) + 1) [ if n > 0 ] = G [ otherwise ]

The first term expands to

F(n) = n * F(n - 1) + n^2 + n

This is O(n! + n^3 + n^2 + nG) = O(n! + nG) as you proposed.

I hope this is helpful.

Upvotes: 1

Related Questions