If you are a visual learner, I have included a graph to help you spot which algorithm is taking more time than other algorithms. You can clearly see that any of the polynomial notations ( `n!`

, `2^n`

, `n^2`

) are generally going to take a lot longer than say, `log(n)`

.

N is computation time and n is number of input elements

Some of the other types of time complexities that exist, but are not described in this blog are:

`O(n!)`

— O of n factorial
`O(2^n)`

— O of 2 to the n
`O(nlog(n))`

— O of n log n: Example
`O(sqrt(n))`

— O of square root of n

Feel free to look up these more complex Big O notations.

### Space Complexity

There is also another side to Big O. Instead of focusing on time only, a different aspect can also be inspected — Space complexity. Space complexity is a measure of the amount of working storage an algorithm needs during run time.

In this scenario, let’s say that all your friends are in different rooms and you need to keep track of who you’ve talked to so you don’t ask the same person twice. This can be written *in Python3*:

>>> def who_took_my_cookie(my_friends):
... spoken_to = []
... for friend in my_friends:
... if friend not in spoken_to:
... if friend.get('has_cookie'):
... print(spoken_to)
... return friend.get('name')
... else:
... spoken_to.append(friend.get('name')

In this example, the `spoken_to`

list could be as long as there are total friends. This means that the space complexity is `O(n)`

.

Let’s feed this function some input and see who took your cookie:

>>> my_friends = [
... {'name':'Kristen', 'has_cookie':False},
... {'name':'Robert', 'has_cookie':False},
... {'name':'Jesse', 'has_cookie':False},
... {'name':'Naomi', 'has_cookie':False},
... {'name':'Thomas', 'has_cookie':True}
... ]

>>> cookie_taker = who_has_my_cookie(my_friends)
['Kristen', 'Robert', 'Jesse', 'Naomi']
>>> print(cookie_taker)
Thomas

*Summary of Space Complexity*: Space complexity can have as many notations as time complexity. This means that the `O(n^2)`

, etc. also exists and can be calculated using the same general principles. Be careful though, time and space complexities may be different than each other for a given function.

By combining time complexity with space complexity, you can begin to compare algorithms and find which one will work best for your constraints.

### Battle of the Algorithms

“Which algorithm will win?!”

Now that you know what time and space complexities are and how to calculate them, let’s talk about some cases where certain algorithms may be better than others.

A simple example to clearly define some constraints would be to examine a self-driving car. The amount of storage in the car is finite — meaning that there is only so much memory that can be used. Because of this, algorithms which favor low space complexity are often favored. But in this case, fast time complexities are also favored, which is why self-driving cars are so difficult ot implement.

Now let’s examine something like a cellphone. The same storage limitations are in place, but because the cellphone isn’t driving around on the street, some sacrifices in time complexity can be made in favor of less space complexity.