Let's talk about "Big O Notation"

When I was young, a history teacher told me: "History is told, because we need to know where we come from and where we are going." And this is something that I use to say to my colleagues. It's never enough to know the latest framework or the last benefits of a programming language. Also, it is important to know(at least a little) the foundations of what is going to be built.

One of the foundations is the well know "Von Neuman" architecture. Many decades ago, Pennsylvania University started the Development of EDVAC. This computer was meant to be used in ballistic calculations by the US Army. In 1945, John Von Neuman in a document called "First Draft of a Report on the EDVAC" described that the logical architecture for this computer should follow:

• Input

• Output

• Control Unit

• Arithmetic Logic Unit

• Memory

This logical architecture is not only used for this computer but also the basic architecture for so many computers used today(unless we are talking about quantic computers).

Why do I mention all this? Well, when we are talking about algorithms, associated with it is the Big O Notation. This notation allows to us describe the complexity of a function respecting time and space based on its input using an asymptotic function for that. When this asymptotic function describes the time complexity then the Control Unit and the Arithmetic Logic Unit are going to lift this load. But when this asymptotic function describes the space complexity then the memory is going to lift this load. With all these topics clear I want to continue this article focused more on space complexity.

Let's assume the following pseudo code to calculate the ith Fibonacci number:

(Fibonacci code)

Fib(n) : Integer {
if(n == 0 or n == 1) {
    return 1;
 }else{
     return Fib(n-1) + Fib(n-2)
 }
}

Based on the above code, to calculate Fibonacci in 7 the tree of all possible visited values is as follows:

I used https://recursion.vercel.app/ to generate the tree, I want to thanks to the creator.

The yellow nodes represent values that are visited/calculated more than once. As can be seen, the value of 0,1, 2, 3, 4 are calculated multiple times. Depending on the mechanism to release memory, these values can last more or less time in memory. But, because the implementation of this example is recursive, all the yellow nodes do not prevail in the same call stack that is represented from the root of the tree to a leaf. The maximum number of objects in memory is proportional to the input of the algorithm. Therefore the space complexity is O(n).

Because of this, its important always explore to found out a better solution about complexity.