Time Complexity of Recursion

We assume that in any case out program takes one unit of time for execution. We don't take seconds since it will depend from machine to machine.

• If a statement is repeated multiple times, then you count the frequency of how many times it is executed.

In this function, we assume printf() takes one unit of time. Since it is making three recursive calls (because n = 3), we can say that it takes three units of time.

It takes n units of time, depending on the value passed, so we can note it as O(n)

void fun1(int n) {
  if (n > 0) {
    printf("%d", n);
    fun1(n - 1);
  }
}

void main() {
  int x = 3;
  fun1(x);
}

Finding Time Complexity using recurrence relation

Using the recurrence relation, we assume that the time taken by this function is T(n). T is for time. The total time of a function should be a sum of all the times taken by the statements inside.

void fun1(int n) {        // T(n)
  if (n > 0) {            // 1
    printf("%d", n);      // 1
    fun1(n - 1);          // T (n - 1)
  }
}

// T(n) = 
// n = 0 = 1
// n > 0 = T(n) = 1 + n
// This can also be written as O(n)

void main() {
  int x = 3;
  fun1(x);
}