How to Find the Complexity of an Algorithm with Example

by

Finding the complexity of an algorithm basically involves analyzing its time and space requirements in relation to the size of its input. Time complexity analysis mainly focus on how much execution time will be taken by an algorithm. And the space complexity mainly focus on the amount of memory usages by an algorithm.

Time Complexity

Time complexity measures how the execution time of an algorithm increases with the size of the input. It’s often expressed using Big O notation, which describes the upper bound of the algorithm’s growth rate. Common time complexities include O(1) for constant time, O(n) for linear time, O(n^2) for quadratic time, and so forth.

Space Complexity

Space complexity measures how much memory an algorithm needs in relation to the input size. Like time complexity, it’s often expressed in Big O notation. It considers both the space taken up by the algorithm’s variables, data structures, and the call stack (in case of recursive calls).

Relationship between Time and Space Complexities

Time and space complexities are related but independent aspects of an algorithm’s efficiency. And these are inversely proportional. It means that if we optimize time complexity, space complexity will increase. And if we optimize space complexity, time complexity will increase.

We can also explain it as An algorithm can be fast but use a lot of memory it means that an algorithm can have low time complexity but will have high space complexity. Similarly An algorithm will become slow when we optimized it to use minimal memory. Means an algorithm will have high time complexity for the low space complexity. So while optimizing an algorithm, we have consider both factor and balance the both factors.

Example: Merge Sort vs. Bubble Sort

Consider two sorting algorithms: Merge Sort and Bubble Sort.

  • Merge Sort:
    • Time Complexity: O(n log n) – It divides the array into halves recursively and merges them, requiring log n divisions and linear time merging.
    • Space Complexity: O(n) – It requires additional space for the temporary arrays used during the merge process.
    • Trade-off: Merge Sort is fast but uses more memory.
  • Bubble Sort:
    • Time Complexity: O(n^2) – Each element is compared with others in nested loops, leading to quadratic time complexity.
    • Space Complexity: O(1) – It sorts the array in place and requires only a constant amount of additional memory.
    • Trade-off: Bubble Sort is slower for large datasets but very memory efficient.

In these examples, Merge Sort is faster but less space-efficient, especially for large arrays, while Bubble Sort is slower but uses minimal additional memory. This contrast highlights the trade-off between time and space complexities in algorithm design.

Example to find the complexity of an algorithm

Consider a basic linear search algorithm in an array:

Linear Search Algorithm

The linear search algorithm iterates over all elements in an array to find a specific element. Here’s a simple implementation in pseudocode:

Algorithm: 
LinearSearch(arr[], element)
   for each item in arr
       if item equals element
           return the index of item
   return -1

Analyzing Time Complexity

  1. Loop Iteration: The algorithm iterates through each element of the array. If there are n elements in the array, it performs n comparisons in the worst case (when the element is not present or it is present at the end of the array).
  2. Time Complexity: Since the number of comparisons is directly proportional to the number of elements, the time complexity is O(n), where n is the size of the array. This is a linear time complexity.

Analyzing Space Complexity

  1. Fixed Memory Usage: The space used by the algorithm is for the array and a few variables for iteration and comparison. This space does not change with the size of the input array.
  2. Space Complexity: Since the additional space required is constant and does not depend on the input size, the space complexity is O(1), which is constant space complexity.

Conclusion

  • Time Complexity of Linear Search: O(n)
  • Space Complexity of Linear Search: O(1)

This example shows that the linear search algorithm has a linear time complexity and a constant space complexity. The method of analysis involves examining how the algorithm’s operations grow with respect to the input size.