You may have noticed :.6f in the f string. That just means format the execution_time value to 6 decimal places.

The code above should have output the execution time like this:

Execution time: 0.000004 seconds

Now, let's run that same code but increase the size of the input each time. Here are the results:

Iterations	Execution Time (seconds)
10	0.000004
100	0.000014
1,000	0.000123
10,000	0.001391
100,000	0.013855
500,000	0.071697
1,000,000	0.153560
5,000,000	0.659647
10,000,000	1.408914

Here is a graph of the results:

The important thing to understand here is that this graph is a straight line.

This means that the amount of time this program takes increases proportionally with the size of the input.

If you double the input, you double the time.

If you triple the input, you triple the time.

Therefore we say this program has linear time complexity.

Linear time complexity is expressed in Big O notation like this: O(n)

Big O uses total operations, not time

In the table above, the time increased as we gave the program more input. But what big O is really concerned with is how many times the loop ran, not how much time.

For 10 items, it looped 10 times. For a million items, it looped a million times. The exact time doesn't matter as much as how the work grows with the input.

That’s what Big O measures. Not seconds, but how many steps the code takes as input increases.

In other words, big O is a way to see how the total number of operations a program does will scale as we increase the size of the input passed to the program.

This makes Big O useful on any machine, with any input size. It helps us think about how code scales, not just how fast it runs right now.

Other time complexities

Not all programs are O(n), here is are a few other time complexities:

O(1)
This is constant time complexity. If your program always completes the same amount of operations regardless of input size then it has a constant time complexity.

O(n)
This is linear time complexity. This is the one we covered in the example above. Your program has linear time complexity if the total amount of operations the program does increases proportionally to input data (n).

O(n²)
This is quadratic time complexity. It means the total amount of operations grows proportionally to the square of the input size. In practice, as the input size increases, the program slows down significantly faster than with linear complexity.

O(log n)
This is logarithmic time complexity. As the input size increases, the total number of operations grows, but at a decreasing rate. In other words, each additional increase in input adds fewer and fewer operations to the overall operations count.

Here is a graph showing these different time compexities.

In the next lesson we are going to analyze the time complexities of different array operations.

Big O Notation