Time and Space Complexity in Computer Algorithms

 What Is Time and Space Complexity in Computer Algorithms?

Are you interested in learning about time and space complexity? We share what is time and space complexity in computer algorithms right here. 

In computer science, time and space complexity are fundamental concepts used to analyze the performance of algorithms. Time complexity refers to the amount of time an algorithm takes to solve a problem, whereas space complexity refers to the amount of memory an algorithm requires to execute. Understanding these concepts is crucial for designing efficient algorithms and evaluating their effectiveness.

What Is Time Complexity?

Time complexity is generally expressed in terms of Big O notation, which describes the worst-case scenario for an algorithm's running time. In other words, big O notation represents the upper bounds of the growth rate of an algorithm's running time relative to the input size. The input size may be the length of an array, size of an integer or any value relating to how large (or small) the input is. This value is usually represented with the letter ‘n’.

Therefore, it tells us how the run time of an algorithm rises as the input size increases. For instance, if we have an algorithm with an O(n) time complexity, where n is the input size, we can expect the algorithm's running time to increase linearly with the input size. In simple words, if the running time was graphed against the input size ‘n’, we would get a straight line showing linear growth.

Time Complexity Notations

Other common time complexity notations include O(1), O(log n), O(n log n), O(n²), and O(2ⁿ).

O(1) refers to constant time complexity, meaning that the algorithm's run time does not depend on the input size. This is typically the most desirable time complexity, ensuring that the algorithm will execute quickly regardless of the input size. An example would be accessing a value in an array using the index.

O(log n) and O(n log n) refer to logarithmic and log-linear time complexity, respectively, and are commonly associated with divide-and-conquer algorithms like binary search and merge sort. Binary search, used for searching a value in a sortedarray, divides the array into two until it finds the value. This means that for each iteration, the length of the array is halved. In the worst case, we would have to search until the length is 1. So how many times is the array divided (into two) until it cannot be divided (length becomes 1)? The answer is log₂ n times where n is the length of the array. This is a common way of getting the time complexity of an algorithm.

Merge sort functions by diving an array into ‘n’ sub-arrays which consist of just a simple algorithm. This division, like binary search, also functions by dividing the array into two parts (taking log₂ n time). However, these subarrays are then sorted by ‘merging’ them (a whole another algorithm) which works in O(n). So, the net time complexity would be O(log n * n) or O(n log₂ n)

O(n²) represents quadratic time complexity, which is associated with algorithms that perform two nested loops over the input, such as bubble sort or selection sort.

O(2ⁿ) represents exponential time complexity, which is typically associated with brute force algorithms that explore all possible combinations of the input. This time complexity increases very fast and even small changes in the input size cause massive time delays. An example would be running the Fibonacci sequence using recursion (extremely inefficient!).

Time complexity can be a great way of comparing algorithms which have the same output. A great example would be the Fibonacci sequence. Using recursion, the time complexity is O(2ⁿ) but using a formula, the time complexity is reduced to O(log n)! This shows how great an impact the choice of algorithm can have. The actual time taken (on my laptop) for calculating the 40^th term (n=40) is given below:

Recursion:    2.9702325 s                      Formula:       0.0005284 s

 

Now, for an interesting question I posed to myself, is it possible to have O(1/n) time complexity. This basically means the time taken would be more for smaller ‘n’ than for larger ‘n’. This is generally considered to be impossible but…

I have made an O(1/n) algorithm!!! Technically, this algorithm has O(1/n) time complexity but the value of ‘n’ may be a bit unusual. The algorithm generates an array of numbers from 0 to 1 with increments of n. For example, n=0.2 would generate [0, 0.2, 0.4, 0.6, 0.8, 1.0]. Here, the iterations done are 6. However, for smaller n, say n=0.01, the algorithm will have 101 iterations.

So, does this algorithm really have O(1/n) time complexity? Technically yes, but it all depends on what ‘n’ is. If you take the increment value as 1/n, this algorithm is simply O(n). But more importantly, this algorithm has no ‘real’ purpose and was just designed for fun!

What is Space Complexity?

On the other hand, space complexity refers to the aggregate memory an algorithm requires to execute. Space complexity is generally expressed in terms of big O notation, similar to time complexity. However, space complexity is often less of a concern than time complexity, as modern computers have ample memory, and algorithms can often be optimized to use less memory. Space complexities are calculated similarly to time complexity but are often not even considered.

Conclusion

In general, it is important to consider both time and space complexity when designing algorithms. A good algorithm should be optimized for both time and space complexity, as well as accuracy and simplicity. By understanding these concepts and their associated notations, developers can design and analyze efficient and effective algorithms for a wide range of inputs and use cases.