DEV Community

Angelo
Angelo

Posted on

1

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.

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay