Here are the fix common shapes of call trees. Of course, there are other kinds as well.

Example 1: Factorial

Only one recursive call from each call, the runtime does not depend on n, n decreases by a constant amount (i.e., 1) with each call

In [1]:
def fact(n):
    if n == 0:
        return 1
    return n*fact(n-1)

n+1 calls in total. Complexity: O(n).

   0
   |
   1
   .
   .
   .
   |
  n-2
   | 
  n-1
   | 
   n

Example 2: Fast exponentiation

Only one recursive call from each call, the runtime does not depend on n, n decreases by a constant factor (e.g., a factor of 2) with each call.

In [2]:
def power(x, n):
    if n == 0:
        return 1
    if n == 1:
        return x
    half_power = power(n//2)
    return half_power*half_power

log2⁡(n)+1 calls in total. Complexity: O((logn))

Call tree:

   0
   |
   1
   .
   .
   .
   |
  n/4
   | 
  n/2
   | 
   n

Example 3: Slow 2n

Two recursive calls from each call, the runtime for each call does not depend on n, n decreases by 1 every time.

In [3]:
def slow_power_2(n):
    if n == 0:
        return 1
    return slow_power_2(n-1) + slow_power_2(n-1)

1+2+4+...+2n)=(1−2n+1)/(1−2)=2n+1−1 calls in total, i.e., O(2n) calls.

Call tree:

 0  0  0 0  0  ...                              0
    1   1 1 1 1 1 1 1 1 ....            1
       ...........

            n-2 _  n-2   n-2  n-2
                 \/        \/ 
                 n-1    _ n-1
                  \   /
                    n

Example 4: sum_list2

Two recursive calls from each call, the runtime does not depend on n, n is smaller by a factor of 2 every time.

In [4]:
def sum_list2(L):
    '''Return the sum of the list of ints L'''
    if len(L) == 0:
        return 0
    
    if len(L) == 1:
        return L[0]  #the sum of the list is L[0] if L[0] is the only element
    
    mid = len(L)//2 #(the index of the approximate midpoint of the list)
    return sum_list2(L[:mid]) + sum_list2(L[mid:])

Total number of calls: 1+2+4+...+2(log2⁡n)=(1−2(log2⁡n+1))/(1−2)=2n−1

Call tree:

     [1].......[1]...[1]....................[1]              
        .                                   .
         .                                 .
          .                               .
           .                             .
             .                          . 
             [n/4]    [n/4]  [n/4]  [n/4]
               \      /       \     /
                \    /         \   /
                 [n/2]        [n/2]
                   \          /
                    \        /
                     \      /
                      \    /
                        [n]

Now, each call sum_list2(L) will take a time proportional to the length of L, so that, like in the analysis of MergeSort, the runtime here will be O(nlog⁡n). However, if we imagine that we get away with doing slicing for free, the runtime will be O(n), since the number of calls is O(n).

Here is how we could get away with not using slicing:

In [5]:
def sum_list2_fast(L, start, end):
    if end == start:
        return 0
    if end == start + 1:
        return L[start]
    
    mid = (start+end)//2
    
    return sum_list2_fast(L, start, mid) + sum_list2_fast(L, mid, end)

def sum_list2_fast_noargs(L):
    return sum_list2_fast(L, 0, len(L))

Example 5: MergeSort

Call tree:

                                                          level
   [1].......[1]...[1]....................[1]            log_2 n +1
    .                                   .
     .                                 .
      .                               .
       .                             .
         .                          . 
         [n/4]    [n/4]  [n/4]  [n/4]                         3
           \      /       \     /
            \    /         \   /
             [n/2]        [n/2]                               2
               \          /
                \        /
                 \      /
                  \    /
                    [n]                                       1

Runtime: O(nlog⁡n).