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
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++){
...
}
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(...){
}
}
}
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)