Time Complexity Analysis of Recursive Functions

The analysis of a recursive function involves finding an asymptotic upper bound on the running time.

• Many algorithms use recursion, and analyzing their time complexity often leads to a recurrence relation. A recurrence relation expresses the running time for an input of size n in terms of the running time for smaller input sizes.
• For example, in Merge Sort, the array is divided into two halves, each half is sorted recursively, and the results are then merged. This leads to the recurrence relation T(n) = 2T(n/2) + cn where the term cn represents the time required to merge the two sorted halves.

Consider the following code for example.

void fun(int n) {

    if (n <= 1)
        return;

    fun(n / 2);
    fun(n / 2);

    for (int i = 0; i < n; i++) {
        cout << "GFG ";
    }
}

#include <stdio.h>

void fun(int n) {
    if (n <= 1)
        return;
    fun(n / 2);
    fun(n / 2);
    for (int i = 0; i < n; i++) {
        printf("GFG ");
    }
}

public class Main {
    public static void fun(int n) {
        if (n <= 1)
            return;
        fun(n / 2);
        fun(n / 2);
        for (int i = 0; i < n; i++) {
            System.out.print("GFG ");
        }
    }
}

def fun(n):
    if n <= 1:
        return
    fun(n // 2)
    fun(n // 2)
    for i in range(n):
        print('GFG', end=' ')

using System;

class Program {
    static void fun(int n) {
        if (n <= 1)
            return;
        fun(n / 2);
        fun(n / 2);
        for (int i = 0; i < n; i++) {
            Console.Write("GFG ");
        }
    }
}

function fun(n) {
    if (n <= 1)
        return;
    fun(Math.floor(n / 2));
    fun(Math.floor(n / 2));
    for (let i = 0; i < n; i++) {
        process.stdout.write('GFG ');
    }
}
fun(8);

The time complexity of this function is written as T(n) = 2T(n/2) + O(n). Now to find the time complexity, we need to solve this recurrence. There are mainly three common methods used to solve recurrence relations that arise in the analysis of recursive algorithms.

• Substitution Method : We guess the form of the solution and prove it using mathematical induction.
• Recurrence Tree Method : This method represents the recurrence as a tree and computes the total cost by summing the cost at each level.
• Master Theorem : The Master Theorem provides a direct way to solve divide-and-conquer recurrences of the form:
  T(n) = aT(n/b) + f(n).