# How to verify the time complexity of your algorithm?

Probably most of you already know how to use Big-O notation to estimate the time complexity of your algorithm, but how do you prove it?

## Calculation speed of modern computers #

Let's start with knowing the calculation speed of modern computers. Nowadays, `10^8` operations can be performed within a second by an average computer. As a result, it basically implies that your algorithm can finish the task in 1 second for the below cases:

1. when you claim the time complexity of your algorithm is `O(N)` or `O(NlogN)` => size of your input `N` can be between `10^6` to `10^8`.
2. when you claim the time complexity of your algorithm is `O(N^2)` => size of your input `N` can be up to `10^4` (cause `10^4 * 10^4 = 10^8).
3. when you claim the time complexity of your algorithm is `O(N^3)` => size of your input `N` can be up to `500` (cause `500 * 500 * 500 ~= 10^8).

## Track how long an operation takes #

In JavaScript, you can make use of `console.time()` and `console.timeEnd()` functions to track the time your algorithm takes, by doing as follows:

``console.time('super-algorithm');superAlgorithm();console.timeEnd('super-algorithm');// => super-algorithm: 60.403ms``

## Examples #

Given two arrays `n1` and `n2`, find each element of `n2` in `n1` and return another array containing the first occurence index of `n1`.

• `O(N^2)` solution
``function find(n1, n2) {  let result = [];  for (let i = 0; i < n2.length; i++) {    for (let j = 0; j < n1.length; j++) {      if (n2[i] == n1[j]) {        result.push(j);        break;      } else if (j == n1.length - 1){        result.push(-1);      }    }  }  return result;}``

Verify the consuming time when the input size is <10^4

``let testArr1 = [], testArr2 = [];for (let i = 0; i < 10 ** 4; i++) {  testArr1.push(i);  testArr2.push(i);}console.time('find');find(testArr1, testArr2);console.timeEnd('find');// => find: 89.401ms (< 1 second)``

Verify the consuming time when the input size is >10^4

``let testArr1 = [], testArr2 = [];for (let i = 0; i < 10 ** 5; i++) {  testArr1.push(i);  testArr2.push(i);}console.time('find');find(testArr1, testArr2);console.timeEnd('find');// => find: 8201.013ms (> 1 second)``
• `O(N)` solution
``function find(n1, n2) {  let result = [];  let map = {};  for (let i = 0; i < n1.length; i++) {    const currNum = n1[i];    if (currNum in map) {      continue;    } else {      map[currNum] = i;    }  }  for (let j = 0; j < n2.length; j++) {    if (n2[j] in map) {      result.push(map[n2[j]]);    } else {      result.push(-1);    }  }  return result;}``

Verify the consuming time when the input size is <10^7

``let testArr1 = [], testArr2 = [];for (let i = 0; i < 10 ** 7; i++) {  testArr1.push(i);  testArr2.push(i);}console.time('find');find(testArr1, testArr2);console.timeEnd('find');// => find: 659.739ms (< 1 second)``

NOTE: The input size supposed can be around `10^8`, but due to the size limit of the key of JavaScript's `Object`, if try with `10^8`, you'll receive `Javascript heap out of memory` error.

Verify the consuming time when the input size is >10^8

``let testArr1 = [], testArr2 = [];for (let i = 0; i < 10 ** 9; i++) {  testArr1.push(i);  testArr2.push(i);}console.time('find');find(testArr1, testArr2);console.timeEnd('find');// => it'll be hanging, I think it's also `JavaScript heap out of memory` error.``

That's it! Try to speak out loud the time complexity of your algorithm in confidence 😤!

🙏🙏🙏 Since you've made it this far, sharing this article on your favorite social media network would be highly appreciated 💖! For feedback, please ping me on Twitter.

Published