The time complexity, in Big O notation, for each function:

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

This function is being called recursively n times before reaching the base case so its O(n), often called linear.

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

This function is called n-5 for each time, so we deduct five from n before calling the function, but n-5 is also O(n). (Actually called order of n/5 times. And, O(n/5) = O(n) ).

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

This function is log(n) base 5, for every time we divide by 5 before calling the function so its O(log(n))(base 5), often called logarithmic and most often Big O notation and complexity analysis uses base 2.

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

Here, it's O(2^n), or exponential, since each function call calls itself twice unless it has been recursed n times.

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

And here the for loop takes n/2 since we're increasing by 2, and the recursion takes n/5 and since the for loop is called recursively, therefore, the time complexity is in

(n/5) * (n/2) = n^2/10,

due to Asymptotic behavior and worst-case scenario considerations or the upper bound that big O is striving for, we are only interested in the largest term so O(n^2).

Good luck on your midterms ;)

T(n) = n*T(n-1) + n

Where T(n) is time taken for input list of size n

This gives O(n!) time complexity. If you expand the relation above, you will get a more precise answer, but the complexity will be O(n!)

The complexity of the first function is exponential. Every recursive call makes 2 new recursive calls. A lot of values are calculated more than once. This is a classic "pitfall", often encountered for instance when writing code for the Fibonacci function.

The second function is a "memoized" version of the first function. All the calculated values are stored in table c, to avoid recalculating them. Thus, the double recursive call max(lcs(X,Y,i,j-1),lcs(X,Y,i-1,j)) doesn't blow up the number of recursive calls, because most recursive calls terminate immediately with "oh, this value has already been calculated, it's in the table".

Okay, the first function you wrote is an example of Exhaustive Search where you are exploring every possible branch that can be formed from a set of whole numbers up to n (which you have passed in the argument and you are using for loop for that). To explain you the time complexity I am going to consider the recursion stack as a Tree (to represent a recursive function call stack you can either use a stack or use an n-ary Tree)

Let's call you first function F1:

F1(3), now three branches will be formed for each number in the set S (set is the whole numbers up to n). I have taken n = 3, coz it will be easy for me to make the diagram for it. You can try will other larger numbers and observe the recursion call stack.

    3
   /| \
  0 1  2    ----> the leftmost node is returns 0 coz (n==0) it's the base case 
    |  /\
    0  0 1
         |
         0   ----> returns 0

So here you have explored every possibility branches. If you try to write the recursive equation for the above problem then:

T(n) = 1; n is 0
     = T(n-1) + T(n-2) + T(n-3) + ... + T(1); otherwise

Here,

T(n-1) = T(n-2) + T(n-3) + ... T(1).

So, T(n-1) + T(n-2) + T(n-3) + ... + T(1) = T(n-1) + T(n-1)

So, the Recursive equation becomes:

T(n) = 1; n is 0
     = 2*T(n-1); otherwise

Now you can easily solve this recurrence relation (or use can use Masters theorem for the fast solution). You will get the time complexity as O(2^n).

Solving the recurrence relation:

T(n) = 2T(n-1)
     = 2(2T(n-1-1) = 4T(n-2)
     = 4(2T(n-3)
     = 8T(n-3)
     = 2^k T(n-k), for some integer `k` ----> equation 1

Now we are given the base case where n is 0, so let,

n-k = 0 , i.e. k = n;

Put k = n in equation 1,

T(n) = 2^n * T(n-n)
     = 2^n * T(0)
     = 2^n * 1; // as T(0) is 1
     = 2^n

So, T.C = O(2^n)

So this is how you can get the time complexity for your first function. Next, if you observe the recursion Tree formed above (each node in the tree is a subproblem of the main problem), you will see that the nodes are repeating (i.e. the subproblems are repeating). So you have used a memory in your second function F2 to store the already computed value and whenever the sub-problems are occurring again (i.e. repeating subproblems) you are using the pre-computed value (this saves time for computing the sub-problems again and again). The approach is also known as Dynamic Programming.

Let's now see the second function, here you are returning answer. But, if you see your function you are building an array named as array in your program. The main time complexity goes there. Calculating its time complexity is simple because there is always just one level of recursion involved (or casually you can say no recursion involved) as every number i which is in range of number n is always going to be less than the number n, So the first if condition gets executed and control returns from there in F2. So each call can't go deeper than 2 level in the call stack.

So,

Time complexity of second function = time taken to build the array;
                                   = 1 comparisions + 1 comparisions + 2 comparisions + ... + (n-1) comparisions
                                   = 1 + 2 + 3 + ... + n-1
                                   = O(n^2).

Let me give you a simple way to observe such recursions more deeply. You can print the recursion stack on the console and observe how the function calls are being made. Below I have written your code where I am printing the function calls.

Code:

def indent(n):
    for i in xrange(n):
        print '    '*i,

# second argument rec_cnt is just taken to print the indented function properly
def F(n, rec_cnt):
    indent(rec_cnt)
    print 'F(' + str(n) + ')'
    if n == 0:
        return 0
    else:
        result = 0
        for i in range(n):
            result += F(i, rec_cnt+1)
        return n*result+n

# third argument is just taken to print the indented function properly
def F2(n, array, rec_cnt):
    indent(rec_cnt)
    print 'F2(' + str(n) + ')'

    if n < len(array):
        answer = array[n]

    elif n == 0:
        answer = 0
        array.append(answer)
    else:
        result = 0
        for i in range(n):
                result += F2(i, array, rec_cnt+1)
        answer = n*result+n
        array.append(answer)

    return answer


print F(4, 1)
lis = []
print F2(4, lis, 1)

Now observe the output:

 F(4)
      F(0)
      F(1)
               F(0)
      F(2)
               F(0)
               F(1)
                            F(0)
      F(3)
               F(0)
               F(1)
                            F(0)
               F(2)
                            F(0)
                            F(1)
                                             F(0)
96
 F2(4)
      F2(0)
      F2(1)
               F2(0)
      F2(2)
               F2(0)
               F2(1)
      F2(3)
               F2(0)
               F2(1)
               F2(2)
96

In the first function call stack i.e. F1, you see that each call is explored up to 0, i.e. we are exploring each possible branch up to 0 (the base case), so, we call it Exhaustive Search.

In the second function call stack, you can see that the function calls are getting only two levels deep, i.e. they are using the pre-computed value to solve the repeated subproblems. Thus, it's time complexity is lesser than F1.

Time complexity is usually defined in big-O notation to signify the asymptotic complexity of the evaluated function, that is, its complexity in the limit.

Let's say that the sizes of the first and second lists are N and M respectively. The recursive step of your function always creates a new sublist of size N-1. This means that the recursion will bottom-out after at most N steps. The termination condition of the function must also perform at most N operations. This means that time complexity of the function is in fact O(N), that is, the number of operations that this algorithm will perform is on the order of N or that it is asymptotically linear in the size of its first argument.

It is not true that recursions are exponential in complexity. In fact there is a theorem that each recursive algorithm has an iterative analogue and vice versa(possibly using additional memory). For explanation on how to do this see here for instance. Also have a look at the section in wikipedia that compares recursion and iteration.

When a recursive function calls itself more than once in some of its flows, you may end up with exponential complexity as is the famous example with fibonacci numbers:

def fib(n):
   if n < 2:
       return 1
   return fib(n - 1) + fib(n - 2)

But this does not mean there is no faster recursive implementation. For instance using memoization you can get that down to linear complexity.

Still recursive implementations really are a bit slower, because the stack frame should be stored when doing a recursive call and it should be restored when returning the value.

def max_v1(lst):
    if len(lst)== 1:
        return lst[0]
    return max(lst[0], max_v1(lst[1:]))

max(...) is O(2), which is called once per max_v1 function call, but the slicing is O(N) for each function call. Hence, we get O(2*N*N) = O(N²).

def max_v2(lst):
    if len(lst)== 1:
        return lst[0]
    l = max_v2(lst[:len(lst)//2])
    r = max_v2(lst[len(lst)//2:])
    return max(l, r)

max_v2 is called twice per max_v2 function call, and each time is passed half of the list, resulting in O(2*N*log(N)), due to the slicing and function calls. max() is called once per function call and therefore gives a total of N*O(2) = O(N). Hence, we get O(N+2*N*log(N)) = O(N*log(N)).