Let us discuss some important examples of time complexity.

Example 1: The following is the program for finding the highest power less than 2. Find its Time complexity.

void f( int n )
{
    while( n != 0 )
    {
        n/=2;
    }
    
}

class DivideByTwo
{
    public static void f(int n)
    {
        while(n != 0)
        {
            n/=2;
        }
    }
} 

def f(n)
{
    while n != 0 :
        n/=2
    
}

Time Complexity: The time complexity of the above program is O(log2n) . This is because at every step we divide n by 2 .

Example 2: The following is the program for finding all the subsets of a given set. Find its Time complexity.

void find_subsets( int arr[] , int n )
{
    for ( int i=0 ; i < pow(2,n) ; i++)
    {
        
        for(int j=0 ; j < n ; j++)
        {
            if((i&(1<
		

class Subsets
{
    public static void find_subsets( int arr[] , int n )
    {
        for ( int i=0 ; i < pow(2,n) ; i++)
        {
            
            for(int j=0 ; j < n ; j++)
            {
                if((i&(1<
		

def find_subsets( arr , n )

    for i in range(0,1<
		

Time Complexity: As can be seen , the outer loop runs O(2^n) times, and the inner loop runs O(n) times. 

Therefore the total time complexity is the multiplication of both i.e. O(2^n * n).

Example 3: Let’s take the example of a fibonacci number. The following program finds the nth fibonacci number. What is its time complexity?

int fib (int n)
{
    if(n <= 1) 
    {
        return 1;
    }
    return fib(n-1) + fib(n-2);
}

class Fibonacci
{
    public static int fib (int n)
    {
        if(n<=1)
        {
            return n;
        }
        else
        {
            return fib(n-1)+fib(n-2);
        }
    }   
}

def fib (n)
{
    if n <= 1:
        return 1;
    return fib(n-1) + fib(n-2);
}

The derivation of the time complexity is slightly non trivial , so you can skip it if you want.

The characteristic equation of the equation ( F(n) = F(n-1) + F(n-2) ) would be x^2 - x -1 =0

Solving the above equation we would get 2 roots.

x= ( 1 + 5 )/2 and x= ( 1 - 5 )/2

As we know the solution of a linear recursive function is given as

F(n) = (1n + 2n )

Using the above fact

• F(n) = ( ( 1 + 5 )/2 ) ^n + ( ( 1 - 5 )/2 ) ^n
• T(n) = O ( ( ( 1 + 5 )/2 ) ^n) + O( ( ( 1 - 5 )/2 ) ^n)
• T(n) = O ( ( ( 1 + 5 )/2 ) ^n)
• T(n) = O ( 1.6180 ) ^n

But is this the best time complexity we can achieve? No , of course not. We can simply use dynamic programming to memoize the above program and bring down the complexity to linear.

int dp[1000];

int fib (int n)
{
    if(n <= 1) 
    {
        return 1;
    }
    if(dp[n] != -1)
    {
        return dp[n];    
    }
    return dp[n] = fib(n-1) + fib(n-2);
}

class Fibonacci
{
    int[] dp = new int[1000];
    public static int fib (int n)
    {
        if(n<=1)
        {
            return n;
        }
        if(dp[n] != 0)
        {
            return dp[n];
        }
        dp[n] = fib(n-1) + fib(n-2);
    }   
}

dp=[0,1]

def fib (int n)
{
    if n < len(dp):
        return dp[n]
    else :
        dp.append(fib(n-1)+fib(n-2))
        return dp[n] 
}

The time complexity of the above program would be linear i.e. O(n).

As there are only ‘n’ distinct states.

We can further reduce the time complexity to O(logn) by using ‘Matrix Exponentiation’.

Example 4: This is a very commonly asked question in the interview. What is the time complexity of the below program?

for( int i = 1 ; i <= n ; i++)
    {
        for( int j = i ; j <= n ; j+=i)
        {
            cout<<"hello";
        }
    }

for( int i = 1 ; i <= n ; i++)
    {
        for( int j = i ; j <= n ; j+=i)
        {
              System.out.println(i);
        }
    }

for i in range(1,n):
    for j in range(i,n,i):
        print("hello")

Even though the time complexity of the above algorithm appears to be O(n*n) , in reality it is actually O (nlogn). You can try to derive it by yourself.

The same principle is used in many famous algorithms like sieve.