Time and Space Complexity

40 views

Getting started learning Data structures and Algorithms. Need a basic understanding of space and time complexity to have better foundation.

In: 2

Time complexity is probably the most common and easiest one to get:

It is basically a measure of how long an algo/operation will take depending on the size of the input.

For example:

You need to read a pre-compiled/pre-computed value? Whatever the size of the input, that value is always immediately available, so it’s constant time O(1).

You need to browse all the values and compute something, looking at each value once on average? Well, however long it’s gonna take to do it once, you will have to do it once per item, that’s linear time O(n)

You can process your data in a divide and conquer kind of way (and look at only one of the divided bits when you divide)? Like if you go through a maze, but there is an arrow towards the path to the exit at each intersection. That’s logarithmic O(log n)

You have to relate every bit of data with every other, each time you add an item, you add N operations, that quadratic time O(n²)

And so one and so forth.

We classify problems based on what the best solution for them is.

Some of these complexities are grouped together because when it becomes huge, we don’t need as much precision. For example, you have P (polynomial time) which is O(n^k), any k.

You have NP (non-deterministic polynomial time), which is a bit harder to write down, but that’s basically :

Either you have an algorithm in P to check that a solution to the problem is correct. Or it’s a divide and conquer algorithm that runs in P when you explore all the branches at once (i.e., only the longest branch matters, not the sum of the branches).

You have EXPTIME which is O(e^n)

Etc.

Space complexity is the same idea but applied to how much memory you need rather than time.

You can speed up some algorithm by caching some results or take less space by recomputing values every time you need them. That’s a trade off, but you could ignore time entirely and just focus on “how low memory can I go”?