Time complexity is represented by O(parameter), where parameter can be a constant, a single variable, a quadratic variable, etc. Time complexity expresses an approximation of the time to execute a certain task.
For example, let's assume that we want to execute console.log('Hi')
in different ways and measure the time to do it.
Time between executions remains (almost) constant.
javascriptlet t0 = performance.now(); console.log('Hi'); let t1 = performance.now(); // t1 - t0 // n = 50 → 0.05 ms // n = 500 → 0.04 ms // n = 1000 → 0.03 ms
In reality, there are slightly time variations between executions as you can see in the graph. The 50th execution took 0.01 ms more than the 500th. But on average, it will take ~0.4 ms to print 'Hi'.
Total time execution depends on n iterations.
javascriptlet t0 = performance.now(); for(let i = 0; i < n; i ++){ console.log('Hi'); } let t1 = performance.now(); // t1 - t0 // n = 50 → 2.02 ms // n = 500 → 21.18 ms // n = 1000 → 39.19 ms
Time grows linearly with the number of iterations. There was one peak at n = 650 (t = 64.91 ms) for some reason that I can't explain.
Total time execution depends on log(n) iterations.
javascriptlet t0 = performance.now(); for(let i = 1; i < n; i = i * 2){ console.log('Hi'); } let t1 = performance.now(); // n = 50 → 0.38 ms // n = 500 → 0.4 ms // n = 1000 → 0.52 ms
Total time execution depends on n·n = n² iterations.
javascriptlet t0 = performance.now(); for(let i = 0; i < n; i ++){ for(let j = 0; j < n; j ++){ console.log('Hi'); } } let t1 = performance.now(); // t1 - t0 // n = 50 → 98.66 ms // n = 500 → 10568.51 ms // n = 1000 → 41761.13 ms
Total time execution depends on n + m iterations.
javascriptlet t0 = performance.now(); for(let i = 0; i < n; i ++){ console.log('Hi'); } for(let i = 0; i < m; i ++){ console.log('Hi'); } let t1 = performance.now(); // n = 50 → 3.97 ms // n = 500 → 45.29 ms // n = 1000 → 77.05 ms
To represent this graph I have assumed that m = n. Therefore, time complexity is O(n + n) = O(2n). As you can see, the results are approximately double as the O(n) graph.
You can find many more examples. I encourage you to play with the browser's console and measure the time that it takes to perform tasks with different complexity.
Hi, I'm Erik, an engineer from Barcelona. If you like the post or have any comments, say hi.