The first step is to work out the recurrence relation:

   T(n) = 3n [this is the preprocessing]
           +
          the average of all possible recursive call costs based on 
          the possible lengths of L2


   Since the length of L2 could be 1, 2, 3, ..., n-2 (note that since
   L1 and L3 are non-empty the most L2 can have is n-2) we end up with

               n-2
   T(n) = 3n + Σ T(i)
               i=1
               ----------
                 (n-2)


The second step is to determine the best asymptotic class this feels like 
it will be and do constructive induction to verify it.  Start with the
Big-O for a class you think feels right.  If that works, then do a Big-Ω
to determine whether you've found the Θ class.