An Introduction to Time Complexity & Space Complexity

In this article we will discuss about Time Complexity & Space Complexity which is very common word for programmers. A lot of peoples get confused while understanding the concept of time-complexity but we will try to understand it in simple way. Lets understand what is Time Complexity and Space Complexity?

Time Complexity:
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. — Wikipedia

In simple words, We can say Time Complexity is the number of operations performed by an algorithm to complete its task (considering that each operation takes the same amount of time).

Space Complexity:
The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm to execute a program and produce output. — Wikipedia

In simple words, We can say Space Complexity is the amount of memory used by the program (including the input values to the algorithm) to execute and produce the result.

Now we have to understand why it is important to know about time and space complexity? Suppose you wrote one program to solve one problem and you want that program should solve the problem in less time and it should not use more space. Then first thing you have to figure it out that what is the time and space complexity of the program? Sometimes, there are more than one way to solve a problem. We need to calculate the performance difference of different approach and choose the best one to solve the problem. While analyzing an code/program, we mostly consider time complexity because the code which performs the task in the smallest number of operations is considered the most efficient one in terms of the time complexity.

Lets understand the above explanation with a simple example. Suppose you are given an sorted array and an integer and you have to find if the integer exists in array or not. To solve this problem we have two algorithms:

1. Linear Search
2. Binary Search

First We will try with Linear Search Algorithm and We will figure it out that what is the time complexity for this algorithm.

class LinearSearch  
{ 
    public static int search(int arr[], int element) 
    { 
        int n = arr.length; 
        for (int i = 0; i < n; i++)  
        { 
            if (arr[i] == element) 
                return i; 
        } 
        return -1; 
    } 
  
    
    public static void main(String args[]) 
    { 
        int arr[] = { 1, 2, 3, 4, 5 }; 
        int x = 5; 
        int result = search(arr, x); 
        if (result == -1) 
        {
            System.out.println("Element is not present in array");
        }
        else
        {
            System.out.println("Element is present at index "+ result); 
        }
    } 
}

Output:

Element is present at index 4

Linear search algorithm will compare each element of the array to the search the given integer. When it finds the integer in the array then it will return index of the integer. Now lets count the number of operations it performs to find out the given integer. Here, the answer is 5 because it compares every element of the array. So, Linear search uses 5 operations to find the given element. In the case of Linear search, this is also known as the worst case of an algorithm. In general, Linear search will take n number of operations in its worst case (where n is the size of the array). From this We can generalize that for an array of size n, the number of operations performed by the Binary Search is: n

Let’s examine the Binary search algorithm for solving the given problem and the time complexity of this algorithm.

class BinarySearch { 
    
    public static int binarySearch(int arr[], int leftIndex, int rightIndex, int element) 
    { 
        if (rightIndex >= leftIndex) { 
            int mid = leftIndex + (rightIndex - leftIndex) / 2; 
            if (arr[mid] == element) 
                return mid; 
            if (arr[mid] > element) 
                return binarySearch(arr, leftIndex, mid - 1, element); 
            return binarySearch(arr, mid + 1, rightIndex, element); 
        } 
        return -1; 
    } 
  
    public static void main(String args[]) 
    { 
        int arr[] = { 1,2,3,4,5 }; 
        int n = arr.length; 
        int element = 5; 
        int result = binarySearch(arr, 0, n - 1, element); 
        if (result == -1) 
        {
            System.out.println("Element is not present in array");
        }
        else
        {
            System.out.println("Element is present at index "+ result); 
        }
    } 
}

Output:

Element is present at index 4

With this approach, We basically ignore half of the elements just after one comparison.

1. First We Compare given element/integer with the middle element.
2. If the given element/integer matches with middle element, we return the mid index.
3. Else If given element is greater than the mid element, then given element can only lie in right half subarray after the mid element. So we recur for right half.
4. Else (element is smaller) recur for the left half.

Now, try to count the number of operations binary search took to find the given element in the sorted array. It took approximately 3 operations. Now, this was the worst case for binary search. This shows that there is a logarithmic relation between the number of operations performed and the total size of the array.

Number of operations = log(5) i.e. 3(approx.) for base 2

From this We can generalize that for an array of size n, the number of operations performed by the Binary Search is: log(n)

From the above two solutions, we can conclude that for an sorted array of size n linear search will perform n operations to complete its task and on the other hand Binary search will take log(n) operations to complete its task. Here we talking about worst case scenario. It is clear that time complexity of linear search is much more than binary search.

I tried to explain about the time complexity with a small example. Time complexity does not matter much on small programs, but when we work on real time projects then we should take care of the time complexity of our program. This is all about the Time Complexity.

For calculating the space complexity for the above two solutions, we need to know the value of memory used by different type of datatype variables, which generally varies from operating system to operating system, but the method for calculating the space complexity remains the same. We just need few extra space to store few values for linear search algorithm. We just compare the given value with the elements in an array one by one. So, Answer is O(1). We just need to store few values i.e. element, leftIndex, rightIndex, mid etc. So, Answer is O(1). The space complexity of Linear Search and Binary Search is O(1).

With this, we come to an end this article on An Introduction to Time Complexity & Space Complexity.