Analysis of Recursion

Let’s go through some examples to get a hang of how to derive time taken $T(n)$ for recursive functions.

def fun(n):
    if n <= 1:
        return
    for i in range(n):      # 𝛳(n)
        print("something")
    fun(n//2)               # T(n/2)
    fun(n//2)               # T(n/2)

function fun(n) {
  if(n <= 1) {
    return;
  }
  for(let i = 0; i < n; i++) {
    console.log('something');
  }
  fun(Math.floor(n/2));
  fun(Math.floor(n/2));
}

Time taken: $T(n) = 2T(n/2) + \Theta(n)$
Base case: $T(1) = C$

def fun(n):
    if n <= 1:
        return
    print("something")      # 𝛳(1)
    fun(n//2)               # T(n/2)
    fun(n//2)               # T(n/2)

function fun(n) {
  if(n <= 1) {
    return;
  }
  console.log('something');
  fun(Math.floor(n/2));
  fun(Math.floor(n/2));
}

Time taken: $T(n) = 2T(n/2) + C$
Base case: $T(1) = C$

def fun(n):
    if n <= 0:
        return
    print(n)        # 𝛳(1)
    fun(n - 1)      # T(n - 1)

function fun(n) {
  if(n <= 0) {
    return;
  }
  console.log(n);
  fun(n - 1);
}

Time taken: $T(n) = T(n - 1) + C$
Base case: $T(1) = C$

Once the value of $T(n)$ is written recursively, we can use Recursion Tree Method to find the actual value of $T(n)$ . Here are the steps for it:

1. Write non-recursive part as root of tree and recursive parts as children.
2. Keep expanding children until a pattern emerges.

$cn$ work is being done at every level.
The work is getting reduced by half in each recursion. Therefore the height of tree is $\log_2 n$ .
Total work done: $cn + cn + cn + \dots \space \log n \space \text{times i.e.} \space cn \log n$ .
Therefore, the time complexity is $\Theta(n \log n)$ .

We are reducing by 1 in each recursion, therefore the height of tree will be $n$ .
Total work done: $C + 2C + 4C + \dots \text{for} \space n$ times.
It’s a geometric progression: $C(1 + 2 + 4 + ... + n)$ .
Therefore, the time complexity is $\Theta(2^n)$ .

Formula for geometric progression:

$$\frac{a *(r^n-1)}{r-1} \\ \text {\footnotesize where r = common ratio, a = first term}$$

Total work done: $C + C + \dots \space \log n$ times.
Therefore, the time complexity is $\Theta(\log n)$ .

Total work done: $C + 2C + 4c + \dots \space \log n$ times.
$C(1 + 2 + 4 + \dots \space \log n) \\ a = 1, r = 2 \\ \text {\footnotesize applying geometric progression formula} \\ \frac {2^{\log n} - 1}{2-1} \\ 2^{\log n } = n$

Therefore, the time complexity is $\Theta(n)$ .

We can still use Recursion Tree method for incomplete trees, but instead of exact bound we’ll get upper bound.

In this example, the left subtree will reduce faster than the right one.
We’ll assume this is a full tree and therefore will get upper bound $O$ instead of the exact bound $\Theta$ .

Total work done: $Cn + 3Cn/4 + 9Cn/16$ and height of tree is $\log n$ .

It’s a geometric progression with ratio less than 1.

Formula for geometric progression with ratio < 1:

$$\frac{a}{1-r} \\ \text {\footnotesize where r = common ratio} \\ \text {\footnotesize a = first term}$$

$a = Cn, r = 3/4$
applying geometric progression formula $\frac {Cn}{1-3/4}$
ignoring constants, the complexity is $n$

The time complexity is $O(n)$ .

It’s not a full tree with height $n$ . Total work done: $C + 2C + 4C + \dots \space \text{for} \space n \space \text{times}$ .
It’s a geometric progression: $C(1 + 2 + 4 + ... + n)$ . Therefore, the time complexity is $O(2^n)$ .