Time Complexity basics in Plain English.

As a software engineer or developer, you might have heard a lot about time complexity. This article will be a summary of time complexity in programming, with examples and explanations for it and its importance. All in plain words.

What is it?

The definition of time complexity is misled by the thought it is an actual time needed for the algorithm to execute. It’s not. While the actual time can depend on several inputs like programming language and the software, the term itself can be described in multiple ways, such as:

• number of operations to make the task done,
• amount of time for the function/code to finish the execution (note that it’s not an actual time),
• amount of time taken by the algorithm to run the code with given inputs.

Why is it measured?

Imagine you are on the plane and need to find out a doctor (assume there’s only one) from the passengers. There’re several ways to do it:

• You ask every single passenger whether he/she is a doctor and, if not, you ask that person about other passengers.
• You ask every single passenger whether he/she is a doctor and, if not, move to the next one.
• You divide the plane into the right and left parts and ask if the doctor is either on the right or left side. And you divide the chosen part into two again and repeat the process.
• Assuming you know the doctor’s seat, you go to that seat and ask the passenger.

Now, this is where the time complexity matters — each of the possible solutions leads you to the desired result but at a different time.

How is it measured?

You might remember from Linear Algebra, the function of variable x is denoted as f(x), meaning the function of x, where the output was dependent on the value of x.

There are two important inputs that matter in time complexity:

1. The number of people on the plane, and
2. The number of operations to make to find out the doctor.

Now that relation is called Order of growth and denoted as O(n) where the n is the number of inputs (people, in this case). That O(n), as in Algebra, defines the output, the time complexity in this case, also called Big O notation.

There are many types of time complexities, here are the most known ones:

— O (1), constant time

— O (n), linear time

— O (log n), logarithmic time

— O (n²), quadratic time

— O (n³), cubic time

Now, let’s return to the doctor on the plane example again and check the time complexity for several inputs: 1, 10, 100, and 1000 people on the plane.

See solution #1.

You ask every single passenger whether he/she is a doctor and, if not, you ask that person about other passengers.

With 1 person on a plane, you get the answer in 1 step. With 10 it’s 100 since you ask every each passenger about the other 99 passengers, and so on:

O (n²) complexity table

So the complexity is n², where n is the number of passengers. Its graph can be plotted as:

O (n²) complexity graph.

See solution #2.

You ask every single passenger whether he/she is a doctor and, if not, move to the next one.

The calculation here is as follows:

O (n) complexity table

So the complexity is n (the worst case, where the doctor is the last person you ask). Basically, the number of operations is the initial number of people with its graph plotted as:

O (n) complexity graph

Solution #3 was

You divide the plane into the right and left parts and ask if the doctor is either on the right or left side. And you divide the chosen part into two again and repeat the process.

You split the group into two by 50, knowing only if the doctor is either on the right-hand or left-hand side. You get the side that has the doctor in it and split that group again, and so on until you get the only person remaining.

The calculation here is as follows:

O (log n) complexity table

From the Calculus, you might remember that splitting is all about the logarithms, so the complexity here can be written as log n, basically derived because of the division with its graph plotted as:

O (log n) complexity graph

And finally solution #4:

Assuming you know the doctor’s seat, you go to that seat and ask the passenger.

With any number of people on a plane, you get the answer in 1 step.

O (1) complexity table

So, the graph of the solution is as follows:

O (1) complexity graph

Comparing the solutions, the final graph can be visualized as:

Time complexities graph

The final graph clearly lets you know the algorithm you’ve chosen does significantly matter when it comes to the execution. Basically, the lesser the time complexity, the faster the execution. In the real world, it’s not always possible to have the algorithm executing in O (1) or O (log n) time, but

• knowing the time complexity,
• knowing how to calculate it,
• visualize it

for given input or thinking on a much larger scale, helps you to

• have an efficient code,
• have an efficient and effective design and architecture,
• provide the output faster
• and cheaper,
• become an effective engineer.

I hope, you enjoyed reading it! 🤞

Open for your comments and suggestions in comments 📝.
And feel free to contact me on LinkedIn as well.