How to derive the time complexity from a recurrence relation?

The recurrence relation is a model that helps in calculating time complexity of an algorithm. The process of recursively discovering the time complexity of an algorithm is known as a recurrence relation.

There are different methods to derive the time complexity of the recurrence relation. But we will use the Master theorem The master method is a formula for solving recurrence relations of the form: T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)

Where nn represents the size of the input, a represents the number of subproblems in the recursion, and n/b represents the size of each subproblem. The size of all subproblems is considered to be the same.

Let's look into a program example to derive time complexity

Program example 

#include <iostream>
using namespace std;
// Binary Search Algorithum in C++
int binarySearch(int [], int , int , int );
int main() {
  int BinarySearchArray[] = {2, 4, 6, 11,13};
  int valueToFind = 13;
  int sizeOfArray = sizeof(BinarySearchArray) / sizeof(BinarySearchArray[0]);
  int valueFound = binarySearch(BinarySearchArray, valueToFind, 0, sizeOfArray - 1);
  if (valueFound == -1)
    cout<< "Not exist"<<endl;
  else
   cout<< "Element is exist at index = "<< valueFound<<endl;
}
int binarySearch(int BinarySearchArray[], int x, int lowestValue, int highestValue) {
  while (lowestValue <= highestValue) {
    int middleValue = lowestValue + (highestValue - lowestValue) / 2;
    if (BinarySearchArray[middleValue] == x)
        return middleValue;
    if (BinarySearchArray[middleValue] < x)
       lowestValue = middleValue + 1;
    else
       highestValue = middleValue - 1;
  }
  return -1;
}

Now we will derive time complexity using theT(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n)

the equation to find the time complexity of the binary search program

Let's understand how it works. Suppose we have a sorted array BinarySearchArray =[2, 4, 6, 11,13]

To find the time complexity of a binary search we use the method:

T(n)=T(n/2)+O(1)T(n) = T(n/2) + O(1)

In which we will assign values as:

a=1,b=2,f(n)=1a=1,b=2,f(n)=1

It will implement like this:

f(n)=1=nlogb(a)=nlog2(1)=n0=1f(n)=1=nlog^{b(a)} =nlog2^{(1)}=n^0=1

After solving this equation we will find the complexity as:

(n)=Θ(nlogb(a)log(n))=Θ(logn)(n)=Θ(nlog^{b(a)}log(n))=Θ(logn)

The time complexity of the binary search is Θ(logn)Θ(logn) using the master theorem.

Free Resources

Copyright ©2026 Educative, Inc. All rights reserved