Time and Space Complexity - Big O notation

Time Complexity

Time Complexity is the amount of time taken by a computer program to run a piece of code. It is a helpful technique used by software engineers to estimate how efficient their program is.

How to find time complexity of a program?
Add up the instructions it will execute as a function of the size of input where the input is a very large value.

What does that mean?
Here is an example, below is a small function which prints numbers in increasing order starting from 0 to the number passed to the function.

/**
 * @param {n} 
 */
var printNums= function(n) {
    for(i = 0; i <= n; i++){
       console.log(i);
    }    
};

The number of instructions executed by this program is n + 1 since the for loop is executed n + 1 times. Now imagine if n is a very large number like 1 million. The value of n is a very large amount as compared to 1 in n+1 so we ignore the constant value 1 and say that our time complexity is ORDER OF n or O(n).

Lets use another example to see how you can use the concept of time complexity in making your code perform faster.

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice. 


Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

A simple way to solve this problem will be to add each element in the array with each other in all possible combinations to find the target value.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let len = nums.length;
    for(let i = 0; i < len; i++){
       for(let j=1; j<len;j++) 
       if((nums[i]+nums[j]) === target && i !== j) {
          return [i,j];  
       }      
    }
};

Now lets analyze the time complexity of the above function:
Step 1: Count number of instructions execute in the code 2 + len2
Step 2: Remove the constant value, so here we remove 2, the result is len2
Step 3: Assuming that n = len our time complexity for this algorithm is  O(n2)

How can we make this function better? 
We know that HashMap has O(1) time complexity. Can we store the array in a HashMap so that we can avoid the nested for loop and reduce our time complexity to O(n)?

Lets try again:
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let len = nums.length;
    let numsMap = new Map();
    for(let i = 0; i < len; i++){
           numsMap.set(nums[i],i);
    }
     
    for(let i = 0 ; i < len; i++){
        let numVal = target - nums[i];
        if(numsMap.has(numVal) && numsMap.get(numsVal) !== i){
           return  [i, numsMap.get(numsVal)];          
        }
    
};

Now lets analyze the time complexity of the above function again:
Step 1: Count number of instructions execute in the code 2 + 2len
Step 2: Remove the constant values,  so the result is len
Step 3: Assuming that n = len our time complexity for this algorithm is O(n)

Useful video related to time complexity:

Space Complexity

Space Complexity of a computer program is the amount of memory used by the program relative to the input.

How to find space complexity of a program?
Find out the variables used in the program and calculate how the size of the variable changes relative to the input.

What does that mean?
Here is an example, below is a small function which takes in two numbers as parameters and returns the sum.

/**
 * @param {num1, num2} 
 */
var sumNums= function(num1, num2) {
   return num1 + num2 ;   
};

There are no variables assigned in this program so the memory usage of this program does not increase relative to the inputs num1 and num2 so the space complexity of the above function is O(1) or constant.

Lets use another example to see how we can use the concept of space complexity to figure out the memory usage of your program relative to the input to or program.

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice. 


Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let len = nums.length;
    let numsMap = new Map();
    for(let i = 0; i < len; i++){
           numsMap.set(nums[i],i);
    }
     
    for(let i = 0 ; i < len; i++){
        let numVal = target - nums[i];
        if(numsMap.has(numVal) && numsMap.get(numsVal) !== i){
           return  [i, numsMap.get(numsVal)];          
        }
    
};

Here we are using a variable numsMap which increases in size as the size on the nums array increases so assuming that the size of the input array is 'n' the space complexity is O(n). 

Useful links: