Big O notation

Space and Time complexity

Big O notation gives you a rough estimate on how your code will perform using the RAM computation model, which is the most aproximate model for current computation until today. Big O measure time complexity but a parallel but really important concept to keep in mind is called Space complexity this one measures how much memory your code will need to execute.

For example the following code:

int sum(int b, int a)
{
   if (a == 0)
     return 0;
   return a + sum(a - 1 + b);
}

Will run in O(N) that means it will take constant time and it will use O(1) in space. This is backed up by the following analysis. for time complexity:

• There are no loops, but the code uses recursivity to perform its work, the code will execute at least N times.
• For Space, we will use at least N storage as we are using 2 vars 2N but 2 is discarded as it does not add for big values.