Code Time Complexity Explained With Examples

Time complexity. I remember the first time I heard those words and thought "yikes, that's sounds complicated". Fortunately, time complexity isn't as difficult to understand as the word may make it seem, once you see some practicle code examples.

What is Time Complexity / Big-O Notation?

Time complexity simply refers to the worst-case scenario of how slow our code could be running at. When talking about time complexity, you will also hear the term Big O or Big O notation thrown around, which refers to a specific measure of how long are code takes to run. You might here an engineer say:

I just optimized this quadratic time function to run at linear time. Now our code is signficiantly faster; the user experience will be noticeably faster when the user does X now.

Why is time complexity important?

Learning about time complexity helps us better understand and improve the efficiency of our code. The efficiency of our code becomes extremely important when you are shipping code that users of your product rely on. To put time complexity into context, here are some examples:

if a video editing programming has functional but unoptimized code, a process that could finish in 1 minute could take 20 minutes.
if Google's search results slowed down by just 1/4 of a second (think time complexity of code running somewhere in a system), it would lose about 8 million searches a day and lots of revenue!

The Common Types of Time Complexity

Below are some of the most common types of time complexities you will hear about:

O(1) ----- Constant time
O(n) ----- Linear time
O(log n) -- Logarithmic time
O(n^2) --- Quadratic time

Constant time: O(1)

an operation is said to be in constant time if it's time execution always stays the same no matter the input size. Examples of constant time operations:

//Accessing a value in a array or object by it's key no matter the size

var smallList = [1,2,3,4];
smallList[3]  // returns 4 in constant time

var bigList = {1:"anne", 2:"ben", ... 500:"laura"};
numbers[500]  // returns laura in constant time



//Whats the time complexity of running this function? (See invocation times below)
function squareEachNumber(array) {
  for (var i = 0; i < 3; i++) {
    array[i] = array[i] * array[i];
  }
  return array;
}

//Answer: Constant time, since we are only iterating 3 times no matter the input size
squareEachNumber([1,2,3,4,5]);
squareEachNumber([1,2,...,500]);

Linear time: O(n)

an operation is said to be in linear time if it's time execution is directly proportional to input size. Examples of linear time operations:

var smallList  = [1,2,3];
var mediumList = [1,2,3,4,5,6,7]
var bigList    = [1,2...,500];

//What is the time complexity of running this function? (see invocation times below)
function loopTheList(list){
  var numberOfIterations = 0;
  for(var i = 0; i < list.length; i++){
    numberOfIterations += 1;
  }
  return numberOfIterations;
}
//Answer: linear time
loopTheList(smallList);  // 4
loopTheList(mediumList); // 7
loopTheList(bigList);    // 500


//What is the time complexity of running this loop?
//Answer: linear time
var n = 100
for(var i = 0; i < n; i++){
  console.log(i)
}

Logarithmic: O(log n)

an operation is said to run in logarithmic time if the time execution grows at a rate less than linear. Here is an example of logarithmic time:

//This function divides the number by 2 every iteration of the while-loop
function logarithmic(number) {
  var numberOfIterations = 0
  while (number > 1) {
    number = number / 2
    numberOfIterations += 1
  }
  return numberOfIterations
}
//Notice how the execution time is growing at a rate less than linear.
logarithmic(20) // 5
logarithmic(30) // 5
logarithmic(40) // 6
logarithmic(500) // 9
logarithmic(1000) //10

Quadratic time: O(n^2)

an operation is said to run in quadratic time if the time execution is directly proportional to the square of the input size.

var list = [1, 2, 3]
duplicateTheList(list)

//quadratic time function
function duplicateTheList(list) {
  var duplicate = []
  //iterate over each element in list
  for (var i = 0; i < list.length; i++) {
    duplicate[i] = []
    //after creating a new array above,
    //insert every item in the list into it.
    for (var j = 0; j < list.length; j++) {
      duplicate[i].push(list[j])
    }
  }
  return duplicate
}
//input = 3
;[1, 2, 3][
  //output = 9
  ([1, 2, 3], [1, 2, 3], [1, 2, 3])
]

/*
For every iteration of the outer for-loop there are 3 operations that take place inside:
When i is 0, the inner for loop will run 3 operations inside, then i becomes 1
When i is 1, the inner for loop will run 3 operations inside, then i becomes 2
When i is 2, the inner for loop will run 3 operations inside, then i becomes 3 and we stop
*/