Time Complexity of recursive of function

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.