DEV Community

Angelo
Angelo

Posted on

Time and Space Complexity in 2 minutes

Space Complexity: How much memory is used.
Time Complexity: How many operations are executed.

This is my interpretation time and space complexity applied to software development.

Time complexity

Constant Time O(1)

A Constant Time complexity operation would be simply running a statement, or a value lookup in an object.
Example:

arr.pop()
arr[1]
5 + 3
4 * 2

Enter fullscreen mode Exit fullscreen mode

Logarithmic O(logn)

With each loop you cut your decrease you work in half, or by a fraction.
A good example of this would be a binary tree. With each step into the search we should be eliminating a fraction of the tree.
So our Time complexity is decreasing by a fraction each time.

Linear O(n)

Linear time complexity, looping through values of an array.

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for(let i = 0; i <= array.length; i++){
 ...
}
Enter fullscreen mode Exit fullscreen mode

An array has a start and end. The operation would run across the array. Resulting in a complexity of O(10), which is not complex at all.
In the above example, n represents the number of items in our array.

Quadratic O(n^2)

Quadratic time complexity, a loop, in a loop, in a loop.

for(...){
  for(...){
    for(...){
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

The above results in 0(n^3)

Exponential O(k^n)

Exponential time complexity refers to an algorithm whose growth doubles with each loop.

Space complexity

Space complexity deals with space an algorithm takes up in memory.
As a trade off to executing a Quadratic Time Complex algorithm, we could create a hash table which is stored in memory.
Now, with our hash table in memory, we can run a Constant or Linear time algorithm against the hash table.
As a trade off, we have increased the Space Complexity by keeping a hash table in memory and decreased the Time complexity or our algorithm.

Top comments (0)