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 number of iterations 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 amount of iterations.

If you double the iterations, you double the time.

If you triple the iterations, 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)

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 takes the same amount of time 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 amount of time it takes to complete the program increases proportionally to input data (n).

O(n²)
This is quadratic time complexity. It means the time it takes to run the program 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 time taken grows, but at a decreasing rate. In other words, each additional increase in input adds less and less to the overall processing time.

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