Big O Notation and Time and Space Complexity

Way of showing how the time it take to execute the program increases when the size of input increases.

Time Complexity

Types

O(1) =  Constant time complexity

O(n) = Linear time complexity

O(n²) = Quadratic time complexity

How to find

Just count the operations per execution for different sizes of n, assignment, conditional checks, calculations etc and count their multiple of n.

   public int Sum(int[] arr)
        {
            var total = 0; // 1 Assignment
            foreach (var elem in arr) // n Assignments
            {
                total = total + elem; // n (assignments) + n (additions)
            }

            return total; // 1 return
        }
  

Whole equations will be 1 + n + 2n + 1 = 3n + 2 = O(n) after dropping constants.

Space Complexity

How much memory (RAM) will the code consume/increases depends upon the input we provide that to code.

• Primitive variable initialization takes up a memory, 
• any array or string takes N memory depending on the size.
• Classes memory is upto Sum of memory of all the variables inside it.

Variables in the loop/block are counted as O(1) because they are destroyed after the interaction in the modern languages. 

  public int Sum(int[] arr)
        {
            var total = 0; // 1 Assignment
            foreach (var elem in arr) // n Assignments
            {
                total = total + elem; // O(1)
            }

            return total;
        }

So it has Constant O(1) space complexity; Note: time complexity is prioritized over space complexity because processor are costlier, more resource intensive than the ram/memory and time is more expensive than the chips :P