Algorithm Complexity and Big O Notation
Let’s discuss algorithms complexity, and in particular how we measure it in the context of algorithms.
Different algorithms, given the same problem to solve and the same inputs, take a different time to solve the problem.
Sometimes, a hugely different time, especially as the number of elements they need to manage grows.
This complexity is called Big O, for no other reason that we use an upper case o
letter as a convention: O(n)
, O(1)
and so on.
The most popular measures of Big O you will see, sorted by more efficient to less efficient, are:
O(1)
O(log n)
O(n)
O(n * log n)
O(n^2)
O(n!)
where n
is the number of inputs. For example, if you need to sort 2 items n
is 2, and if you need to sort 20.000 items, n
is 20.000.
But you don’t need to substitute the value in the O()
calculation. That is a symbol, meant to signal developers and everyone looking at the algorithms its efficiency.
An algorithm with O(1)
efficiency is the best possible one we can find. The time to execute does not depend on the number of inputs, it always takes the same time to execute
An algorithm with O(n)
scales linearly with the number of inputs. If with 10 items it takes 1 second, with 100 items it will take 10 seconds.
An algorithm with O(n^2)
, if with 4 items takes 16 seconds, with 10 items takes 100 seconds.
We will analyze and calculate the Big O efficiency of a good number of algorithms in the next lessons.
It’s important to note that Big O notation does not give us all the information we need to judge whether an algorithm will be faster than another, in particular if their Big O value is the same. In this case, you will need to use other tools to test the efficiency.
But when algorithms have different classes (O(n)
vs O(n^2)
for example), there’s no doubt.
THE VALLEY OF CODE
THE WEB DEVELOPER's MANUAL
You might be interested in those things I do:
- Learn to code in THE VALLEY OF CODE, your your web development manual
- Find a ton of Web Development projects to learn modern tech stacks in practice in THE VALLEY OF CODE PRO
- I wrote 16 books for beginner software developers, DOWNLOAD THEM NOW
- Every year I organize a hands-on cohort course coding BOOTCAMP to teach you how to build a complex, modern Web Application in practice (next edition February-March-April-May 2024)
- Learn how to start a solopreneur business on the Internet with SOLO LAB (next edition in 2024)
- Find me on X