O(1), O(n), O(log(n)): simple examples

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.

O(1)

Time between executions remains (almost) constant.

javascript
let 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'.

O(n)

Total time execution depends on n iterations.

javascript
let 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.

O(log(n))

Total time execution depends on log(n) iterations.

javascript
let 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

O(n²)

Total time execution depends on n·n = n² iterations.

javascript
let 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

O(n + m)

Total time execution depends on n + m iterations.

javascript
let 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.