# Runtime Complexity!

Not as complex as you think.

In my previous blog post on memoization, I ended it by comparing the runtimes between recursion without memoization and recursion *with *memoization. The result was two completely different numbers! But what do they really mean?

Well, runtime is self-explanatory. The TIME it takes for the function to RUN. A lot of different factors can take into this such as the hardware it’s running on, but let’s focus just on code efficiency. Take a look at this screenshot from my last blog post.

On the right is the time it took for the functions to finish running on these two separate calls. Without memoization, the lower the number, the faster the runtime. There are equations that help define the different types of runtime. Take a look at some of the more common ones below. n is the amount data you are working with.

`Constant time: 1`

Logarithmic time: log(n)

Linear time: n

Quasi-linear time: n * log(n)

Quadratic time: n ^ 2

Exponential time: 2 ^ n

Let me go ahead and explain these now.

Constant time means that no matter the amount of data you are working with, the runtime stays the same. Constant time is what every programmer wants as their runtime. It is the absolute gold standard. Logarithmic time means that increasing the amount of data wouldn’t proportionally increase the runtime as well. For instance, doubling the amount of data you’re working with does NOT double the amount of runtime. Next is Linear time. Linear time increases the amount of runtime proportionally to the amount of data you input. So if you do double the amount of data, then the runtime is also doubled. Quasi-linear time is the same as linear time, however a little bit more gets added to the runtime of that data, so if you were to double your data, quasi-linear time might take 2.1x the amount of time. Quadratic time significantly increases the amount of runtime with data. Usually comparing an element in that data to all other parts of that data would result in this. Not really a good runtime. Last but definitely not least is exponential time. This DOUBLES the runtime with the introduction of just one new piece of data. Absolutely catastrophic. Do not recommend.