Time and space complexity

Time and space complexity

Benjamin Papadakis's photo
Benjamin Papadakis
·Dec 4, 2021·

2 min read

Subscribe to my newsletter and never miss my upcoming articles

Assume we have 2 different sets of code written differently but solve the same problem and run like this:

{ Code 1 }
# after execution:
runtime: 3 seconds
memory allocated: 20 GB
{ Code 2 }
# after execution:
runtime: 40 seconds
memory allocated: 1 GB

Which do you think is the better code?

What is a way of measuring which code is better?

On the one hand, for the human senses and logic, readability could be a determining factor. Meaning how easily do you understand what the code does just by looking at it.

On the other hand, it can also be scored on "how much time it needs to run until it's finished". However, because the time it needs to run is relative to the hardware of the computer, we will have to go an extra step and take out the time factor and think in terms of operations, instead of time. So although we call this complexity of operations time complexity it has more to do with the computational complexity. So let's try explaining this again.

"Time complexity" refers to the computational complexity of an algorithm's execution time. Assuming that each operation takes a set amount of time, time complexity can be determined by counting how many basic operations the algorithm performs. As a result, the algorithm's execution time and the number of basic operations it performs are assumed to be proportional. (Hopefully, you didn't get lost in the last sentence.)

Another way of measuring code is by space complexity. Space complexity is the amount of memory space needed to run the code. In other words, when an algorithm completes running, it is the amount of memory it had to take up to solve the computational problem.

From the two examples above it depends on what we measure.

Code 1 runs much much faster but needs more memory. So when talking about time complexity this one is better.

Code 2 needs much more time but required a lot less memory. So when talking about space complexity this one is better.

{ Code 1 }
# after execution:
runtime: 3 seconds
memory allocated: 20 GB
{ Code 2 }
# after execution:
runtime: 40 seconds
memory allocated: 1 GB
 
Share this