Big O notation is a mathematical notation that describes theย limiting behaviorย of aย functionย when theย argumentย tends towards a particular value or infinity. The letter O stands forย ๐๐ณ๐ฅ๐ฏ๐ถ๐ฏ๐จ, meaning theย order of approximation.
Big O notation doesn't show theย timeย an algorithm will run. Instead, it shows the number of operations it will perform. Big O notationย is used to classify algorithms according to how their running time or space requirements grow as the input size grows.
๐๐ข๐ ๐ ๐๐ฌ๐ญ๐๐๐ฅ๐ข๐ฌ๐ก๐๐ฌ ๐ ๐ฐ๐จ๐ซ๐ฌ๐ญ-๐๐๐ฌ๐ ๐ซ๐ฎ๐ง ๐ญ๐ข๐ฆ๐
Imagine that you're a teacher with a student named Jane. You want to find her records, so you use a simple search algorithm to go through your school district's database.
You know that simple search takes O(n) times to run. This means that, in the worst case, you'll have to search through every single record (represented by n) to find Jane's.
But when you run the simple search, you find that Jane's records are the very first entry in the database. You don't have to look at every entry โ you found it on your first try.
Did this algorithm take O(n) time? Or did it take O(1) time because you found Jane's records on the first try?
In this case, O(1) is the best-case scenario โ you were lucky that Jane's records were at the top. But Big O notation focuses on the worst-case scenario, which is O(n) for simple search. Itโs a reassurance that simple search will never be slower than O(n) time.
๐ Here are some common algorithms and their complexity in Big O notation:
๐(๐ฅ๐จ๐ ๐ง):ย Binary search
๐(๐ง):ย Simple search
๐(๐ง * ๐ฅ๐จ๐ ๐ง) Merge sort
๐(๐งยฒ):ย Selection sort
๐(๐ง!): Traveling salesperson
On the chart below you may find most common orders of growth of algorithms specified in Big O notation.
BONUS:
A way to remember which is most complex ๐:
๐(๐ฅ๐จ๐ ๐ง) = O(nice)
๐(๐ง) = O(ok)
๐(๐ง * ๐ฅ๐จ๐ ๐ง) = O(not nice)
๐(๐งยฒ) = O(my)
๐(๐ง!)= O(mg!)
--
๐จโ๐ป
๐ I post daily about my data-journey and some tips and resources along the way. Followย David Regaladoย and ring the ๐ for more content.
#softwareengineering #computerscience
