What the heck is Time and Space Complexity

7 min readMay 17, 2019

The time has come to understand Time and Space complexity. For the sole purpose of not jumping into the rabbit hole of the PhD level of this we are simply going to strictly talk about what truly matters to us Computer Science students and software engineers; Big-O.

Back history, Edmund Georg Hermann Landau was a German mathematician who worked with number theory and invented and complex analysis, you can learn more about him here.

If you are interested in learning more in depth PhD level of computational complexity theory here is where you can learn more here.

For the rest of us that like to trim the fat, let’s continue.

Imagine you finished your MVP (Minimum Viable Product), and you have a database of users in arbitrary order. Now you need to search for a user in an array of users of only 100. Not bad it responds quick and finds that user quick. As more users create accounts, the number of users grows to the thousands. Now searching for any specific user takes a little longer because we have to search through that array in linear-time. The program now is not optimal, and is not something to scale. How do you scale to handle a million users, and how would you scale to handle billions of users? It turns out that the answer to this question is to reduce the time and space complexity of your different functions.

So how is your startup going to scale searching through a large arbitrary user/ product-base database. It’s time to analyze the code.

So how do you reduce your code’s complexity?

First you need to investigate this question: “Which parts of my code become slower as the input size grows?”

def example(list):
  for item in list:
    print(item)

Let’s consider the function above. Since this function prints every item in a list, it takes proportionally longer based on the list size, because It has to go through every item in the list, one at a time. Now imagine if the list has one thousand, imagine one million or even one billion. So what does this look like, and what is it called?

In analyzing the complexity of an algorithm, engineers use Big O notation. In our example above, the algorithm’s time complexity is O(n), where n is the number of items in the list.

Is this an efficient algorithm? Well depends what are we measuring for. Efficiency covers a lot of topics:

CPU (time) usage
Memory (Space) usage
disk usage
network usage

These resources are all important however, for this specific algorithm we are seeing the CPU usage; time complexity performance. Now let’s change the code above:

def example(list, value):
  for item in list:
    if item == value:
      print(item)
      break

The code above is asking to find a value within a given list, once found print that item. Fair enough. So what does this mean how are we going to start analyzing the complexity of this code. Well best case scenario is O(1).

“What the heck is order of 1"

Means a constant time is order of 1. Means that no matter what that if the value we are looking for is at the beginning of this list it will always return the first item of the list and not caring for the rest of the list input. But as you know…

Expect the best, plan for the worst, and prepare to be surprised — Denis Waitley

In reality we do not know where this value is in this list. In fact, the word is not guaranteed to be in the list. So, in the worst case, we may have to look through every item in the list to find the value, or be sure it’s not in the list. This is expressed as O(n) where n is the number of items in the list. It turns out that Big-O notation is often simplified to the worst case scenario of an algorithm/ function in terms of space (memory and disk usage) and execution time (CPU usage).

So many annotations are there, which goes from best to worst, which to avoid?

O(1) is considered the best because as the number of operations increases the function will execute in the same amount of time space, no matter the data size. Let’s take a deeper dive into each of these from worst (because we only annotate for the worst case) to best:

O(n!) — Factorial Time

O(n!) algorithms will execute in n factorial time per every new operation. Simply Terrible.

O(2^n) — Exponential Time

O(2^n) algorithms execution time will double with each new element. Caution, this tend to exhaust resources very quickly! Read this article on how I refactored the Fibonacci Sequence from O(2^n) to O(n) here.

O(n²) — Quadratic Time

O(n²) means the function will perform proportionally to the square of the input data size. This often is the case if nested loops are running over the input data performing some tasks on it. Stay tuned for my my next article series “what the heck is sorting” where I go into details about bubble-sort which use O(n²)and other sorting algorithms.

O(n log n) — Log Linear Time

Like O(log n) but multiplied by n variable, making this classification less efficient.

O(n) — Linear Time

O(n) says the algorithm will take a linear time as explained above.

O(log n) — Logarithmic Time

The concept of cutting in half the input data described in a binary search example produces a growth curve that peaks at the beginning and slowly flattens out as the size of the data increase. Doubling the size of the input data set has little effect on its growth as after a single iteration of the algorithm the data will be halved and therefore on a par with an input data half the size. This makes algorithms like binary search extremely efficient when dealing with large data. You can read more about logarithmic time complexity by a student peer from Make School; Jasmine Humbert here.

O(1) — Constant Time

Algorithms that are O(1) will always execute in the same time, the size of the input simply does not matter.

So now that we have a little more knowledge on what time complexity is lets tap into space complexity (memory and disk usage).

Space complexity — a measure of the amount of working storage an algorithm needs. That means how much memory, in the worst case, is needed at any point in the algorithm. As with time complexity, we’re mostly concerned with how the space needs grow, in big-O terms, as the size n of the input problem grows.

This means if you have an O(n) time complexity function you can also have an O(1) space complexity:

def example(list, value):
  for index, item in enumerate(list): # O(n) time complexity
    if item == value:
      return index # O(1) space complexity

As you see above, it takes “order of n O(n)” time to loop through the entire list, based on the worst case. On the flip side it only takes O(1) space, because we will constantly only return one value in this case the index position of the item.

Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.

def example(word_list):
  all_words_with_a = [] # auxiliary space
  for word in word_list: # O(n) time complexity
    if word[0] == 'a':
      all_words_with_a.append(word)
  return all_words_with_a # O(n) space complexity

As you see, we do not know the size of this list of words nor how many words in the list begin with “a”. Space complexity analysis: How many words do we need to keep in memory inside the “all_words_with_a” array before the end of the function?

Best case:
- zero words contain “a” → O(1)

Worst case:
- every word contains “a” → O(n)

There will come a time where you need to decide which is more important for the specific problem you are trying solve. Is speed of the algorithm important or memory usage. These are the type of tradeoffs you need to consider…

So what is more important to optimize for well that is totally up to you…

Hope this article helped, all feedback is accepted. 😃 Don’t forget to drop some claps! 👏👏👏 and stay tuned for my next article series on “what the heck is sorting”!

Research Acknowledgements: