Time Complexity with Simple Examples

Imagine a classroom of 100 students in which you gave your pen to one person. You have to find that pen without knowing to whom you gave it. 

Here are some ways to find the pen and what the O order is.

• O(n²): You go and ask the first person in the class if he has the pen. Also, you ask this person about the other 99 people in the classroom if they have that pen and so on. This is what we call O(n²). 
• O(n): Going and asking each student individually is O(N). 
• O(log n): Now I divide the class into two groups, then ask: "Is it on the left side, or the right side of the classroom?" Then I take that group and divide it into two and ask again, and so on. Repeat the process till you are left with one student who has your pen. This is what you mean by O(log n). 

Is the Time Complexity Same as Time of Execution?

The Time Complexity is not equal to the actual time required to execute a particular code, but the number of times a statement executes.

For example: Write code in C/C++ or any other language to find the maximum between N numbers, where N varies from 10, 100, 1000, and 10000. For Linux based operating system (Fedora or Ubuntu), use the below commands: 

To compile the program: gcc program.c – o program
To execute the program: time ./program

You will get surprising results i.e.:

• For N = 10: you may get 0.5 ms time, 
• For N = 10,000: you may get 0.2 ms time. 
• Also, you will get different timings on different machines. Even if you will not get the same timings on the same machine for the same code, the reason behind that is the current load.

So, we can say that the actual time required to execute code is machine-dependent!

What is meant by the Time Complexity of an Algorithm?

• Instead of measuring actual time required in executing each statement in the code, Time Complexity considers how many times each statement executes. 
• We measure rate of growth over time with respect to the inputs taken during the program execution.

Example 1: Consider the below simple code to print Hello World

#include <iostream>
using namespace std;

int main()
{
    cout << "Hello World";
    return 0;
}

#include <stdio.h>

int main()
{
    printf("Hello World");
    return 0;
}

import java.io.*;

class GFG {
    public static void main(String[] args)
    {
        System.out.print("Hello World");
    }
}

print("Hello World")

using System;

public class GFG{

    static public void Main (){

        // Code
          Console.WriteLine("Hello World");
    }
}

console.log("Hello World")

Hello World

Time Complexity: In the above code “Hello World” is printed only once on the screen. 
So, the time complexity is constant: O(1) i.e. every time a constant amount of time is required to execute code, no matter which operating system or which machine configurations you are using. 

Example 2:

#include <iostream>
using namespace std;

int main()
{

    // Here n is assumed to be user input
    int i, n = 8;
    for (i = 1; i <= n; i++) {
        cout << "Hello World !!!\n";
    }
    return 0;
}

#include <stdio.h>
void main()
{
    // Here n is assumed to be user input    
    int i, n = 8;
    for (i = 1; i <= n; i++) {
        printf("Hello World !!!\n");
    }
}

class GFG {

    public static void main(String[] args)
    {
        // Here n is assumed to be user input
        int i, n = 8;
        for (i = 1; i <= n; i++) {
            System.out.printf("Hello World !!!\n");
        }
    }
}

# Here n is assumed to be user input
n = 8
for i in range(1, n + 1):
    print("Hello World !!!")

using System;
public class GFG {

    public static void Main(String[] args)
    {
        // Here n is assumed to be user input
        int i, n = 8;
        for (i = 1; i <= n; i++) {
            Console.Write("Hello World !!!\n");
        }
    }
}

// Here n is assumed to be user input
let i, n = 8;
for (i = 1; i <= n; i++) {
    console.log("Hello World !!!");
}

Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!

Time Complexity: In the above code “Hello World !!!” is printed only n times on the screen, as the value of n can change. 
So, the time complexity is linear: O(n) i.e. every time, a linear amount of time is required to execute code.

How To Find The Time Complexity Of An Algorithm?

Now let us see some other examples and the process to find the time complexity of an algorithm:

Q1. Find the sum of all elements of a list/array

#include <iostream>
using namespace std;

// A->array and
// n->number of elements in array
int listSum(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i <= n - 1; i++) {
        sum = sum + arr[i];
    }
    return sum;
}

int main()
{
    int arr[] = { 5, 6, 1, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << listSum(arr, n);
    return 0;
}

#include <stdio.h>

// A->array and
// n->number of elements in array
int listSum(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i <= n - 1; i++) {
        sum = sum + arr[i];
    }
    return sum;
}

int main()
{
    int arr[] = { 5, 6, 1, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d", listSum(arr, n));
    return 0;
}

public class Main {
    
    // A->array and
    // n->number of elements in array
    public static int listSum(int[] arr, int n) {
        int sum = 0;
        for (int i = 0; i <= n - 1; i++) {
            sum = sum + arr[i];
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr = { 5, 6, 1, 2 };
        int n = arr.length;
        System.out.println(listSum(arr, n));
    }
}

# A->array and
# n->number of elements in array
def listSum(arr, n):
    sum = 0
    for i in range(n):
        sum = sum + arr[i]
    return sum

arr = [5, 6, 1, 2]
n = len(arr)
print(listSum(arr, n))

using System;

class Program {
    
    // A->array and
    // n->number of elements in array
    static int ListSum(int[] arr, int n) {
        int sum = 0;
        for (int i = 0; i <= n - 1; i++) {
            sum = sum + arr[i];
        }
        return sum;
    }

    static void Main() {
        int[] arr = { 5, 6, 1, 2 };
        int n = arr.Length;
        Console.WriteLine(ListSum(arr, n));
    }
}

// A->array and
// n->number of elements in array
function listSum(arr, n) {
    let sum = 0;
    for (let i = 0; i <= n - 1; i++) {
        sum = sum + arr[i];
    }
    return sum;
}

let arr = [5, 6, 1, 2];
let n = arr.length;
console.log(listSum(arr, n));

<?php

// A->array and
// n->number of elements in array
function listSum($arr, $n) {
    $sum = 0;
    for ($i = 0; $i <= $n - 1; $i++) {
        $sum = $sum + $arr[$i];
    }
    return $sum;
}

$arr = array(5, 6, 1, 2);
$n = count($arr);
echo listSum($arr, $n);
?>

14

To understand the time complexity of the above code, let's see how much time each statement will take:

int list_Sum(int A[], int n)
{
    int sum = 0;    // cost=1  no of times=1
    for(int i=0; i<n; i++)    // cost=2  no of times=n+1 (+1 for the end false condition)
        sum = sum + A[i]  ;     // cost=2  no of times=n 
    return sum ;                // cost=1  no of times=1
}

Pseudocode : list_Sum(A, n)
{
total =0                   // cost=1  no of times=1
for i=0 to n-1             // cost=2  no of times=n+1 (+1 for the end false condition)
    sum = sum + A[i]       // cost=2  no of times=n 
return sum                 // cost=1  no of times=1
}

public class ListSum {

    // Function to calculate the sum of elements in an array
    static int listSum(int[] A, int n) {
        int sum = 0; // Cost = 1, executed 1 time

        for (int i = 0; i < n; i++) { // Cost = 2, executed n+1 times (+1 for
                                      // the end false condition)
            sum = sum + A[i]; // Cost = 2, executed n times
        }

        return sum; // Cost = 1, executed 1 time
    }

    // Main method for testing
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        int length = array.length;
        int result = listSum(array, length);
        System.out.println("Sum: " + result);
    }
}

def list_sum(A):
    sum = 0
    for i in range(len(A)):
        sum = sum + A[i]
    return sum

using System;

class Program
{
    // Function to calculate the sum of elements in a list
    static int ListSum(int[] A)
    {
        int sum = 0; // Initialize sum to 0

        // Loop to iterate through the array elements
        for (int i = 0; i < A.Length; i++)
        {
            sum = sum + A[i]; // Accumulate the sum
        }

        return sum; // Return the calculated sum
    }

    // Driver code
    static void Main()
    {
        // Example usage
        int[] array = { 1, 2, 3, 4, 5 };
        int result = ListSum(array);

        Console.WriteLine(result);
    }
}

function listSum(A) {
    let sum = 0; // Initialize sum to 0

    // Loop to iterate through the array elements
    for (let i = 0; i < A.length; i++) {
        sum = sum + A[i]; // Accumulate the sum
    }

    return sum; // Return the calculated sum
}

// Example usage
let array = [1, 2, 3, 4, 5];
let result = listSum(array);

console.log(result);

Therefore the total cost to perform sum operation 

Tsum=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 =C1 * n + C2 = O(n)

Therefore, the time complexity of the above code is O(n)

Q2. Find the sum of all elements of a matrix

For this one, the complexity is a polynomial equation (quadratic equation for a square matrix)

• Matrix of size n*n => Tsum = a.n² + b.n + c
• Since Tsum is in order of n², therefore Time Complexity = O(n²)

#include <iostream>
using namespace std;

int main()
{
    int n = 3;
    int m = 3;
    int arr[][3]
        = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } };
    int sum = 0;

    // Iterating over all 1-D arrays in 2-D array
    for (int i = 0; i < n; i++) {

        // Printing all elements in ith 1-D array
        for (int j = 0; j < m; j++) {

            // Printing jth element of ith row
            sum += arr[i][j];
        }
    }
    cout << sum << endl;
    return 0;
}

/*package whatever //do not write package name here */

import java.io.*;

class GFG {
    public static void main(String[] args)
    {
        int n = 3;
        int m = 3;
        int arr[][]
            = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } };
        int sum = 0;

        // Iterating over all 1-D arrays in 2-D array
        for (int i = 0; i < n; i++) {

            // Printing all elements in ith 1-D array
            for (int j = 0; j < m; j++) {

                // Printing jth element of ith row
                sum += arr[i][j];
            }
        }
        System.out.println(sum);
    }
}

n = 3
m = 3
arr = [[3, 2, 7], [2, 6, 8], [5, 1, 9]]
sum = 0

# Iterating over all 1-D arrays in 2-D array
for i in range(n):
    
    # Printing all elements in ith 1-D array
    for j in range(m):
        
        # Printing jth element of ith row
        sum += arr[i][j]

print(sum)

using System;

class MainClass {
    static void Main(string[] args)
    {
        int n = 3;
        int m = 3;
        int[, ] arr
            = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } };
        int sum = 0;

        // Iterating over all 1-D arrays in 2-D array
        for (int i = 0; i < n; i++) {
            
            // Printing all elements in ith 1-D array
            for (int j = 0; j < m; j++) {
                
                // Printing jth element of ith row
                sum += arr[i, j];
            }
        }
        Console.WriteLine(sum);
    }
}

let n = 3;
let m = 3;
let arr = [[3, 2, 7], [2, 6, 8], [5, 1, 9]];
let sum = 0;

// Iterating over all 1-D arrays in 2-D array
for (let i = 0; i < n; i++) { 
    
    // Printing all elements in ith 1-D array
    for (let j = 0; j < m; j++) {

      // Printing jth element of ith row
      sum += arr[i][j];
    }
}
console.log(sum);

43

Time Complexity: O(n*m)
The program iterates through all the elements in the 2D array using two nested loops. The outer loop iterates n times and the inner loop iterates m times for each iteration of the outer loop. Therefore, the time complexity of the program is O(n*m).

Auxiliary Space: O(n*m)
The program uses a fixed amount of auxiliary space to store the 2D array and a few integer variables. The space required for the 2D array is nm integers. The program also uses a single integer variable to store the sum of the elements. Therefore, the auxiliary space complexity of the program is O(nm + 1), which simplifies to O(n*m).

In conclusion, the time complexity of the program is O(nm), and the auxiliary space complexity is also O(nm).

So from the above examples, we can conclude that the time of execution increases with the type of operations we make using the inputs.

Related articles:

• Asymptotic Analysis
• Worst, Average and Best Cases
• Asymptotic Notations
• Analysis of Loops
• Amortized Analysis Introduction
• Miscellaneous Problems of Time Complexity
• Practice Questions on Time Complexity Analysis
• Knowing the complexity in competitive programming