Understanding the concept of algorithms is an empowering thing to have in your arsenal. It makes you think about scaling, performance, and being efficient at what you’re doing. You can decrease your workload and the time you spend at your desk.
I’m not an algorithmic or a mathematical expert, but I understand algorithms to increase efficiency at what I’m doing.
In this blog post, I’m going to talk about time complexity. The mathematical notation of the logarithm example I will be using is called the O(log n) notation from the Big O notation family.
O(log n) refers to a function in an amount of time proportional to the logarithm of the size of the input; in other words, O(log n) is a way to measure the run-time complexity for worst-case scenario.
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. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.
Read more: Big O notation
Essentially, a simplified explanation on how the O(log n) notation works is to simply divide and conquer.
Fun Fact: O(log n) is the most common algorithm to use for measuring a binary search.
Binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the sub-array reduces to zero.
Read more: tutorialspoint.com
The truth is that everybody has used this notation at some point in their lives, whether they realize it or not.
A great example is to find the phone number of your favorite restaurant for delivery in a Yellow Page phone book. Generally, you do not browse through every restaurant in the listing in alphabetized order to find the appropriate one. Let’s say for some reason you’re searching from the first page at index A and filtering through every restaurant’s name during the process while your favorite restaurant happens to be called Walter White’s Pizza House – well guess what? Congratulations! You just WASTED all those hours that you’ll never get back. On a related note, I’ve seen sane people lose their minds going through thousands of records in an Excel sheet, one row at time, looking for a single record. Do yourself a favor — use the built-in formulas and search filter to parse records out efficiently!
Instead, most people will divide and conquer naturally when it comes to a phone book – splitting the phone book in half each time by sense and feel until you get to the index W page. Almost everyone is familiar with this approach where you’d only need to explore a fraction of the entire space until you eventually find the restaurant’s phone number.
The same principle can be applied to many problems.
Let’s do a concrete exercise using the concept above to demonstrate what I meant by dividing and conquering. Using the concept above, I am able to predict a number inside anyone’s mind in a timely manner.
So between the numbers from 1 to 1000, pick a number and write it down. With a maximum of 10 attempts I will be able to accurately predict the number inside the person’s head using a series of queries. Regardless what the number is, worst-case scenario will never exceed over 10 attempts.
The objective is to get the median integer of the range between the highest and lowest integers or by using this formula (subtract the higher and lower value from the range, divide the result by 2, then add the result to the lower integer of the range).
If no algorithm existed for this problem, this process would not have been efficient and could not scale.
Let’s do the math and illustrate it out together. I will be the host and you will be the guest. Pretend the guest wrote down the number 676 out of 1000.
- Host: Is the number equal to or higher than 500.
- Host: Is the number equal to or higher than 750.
- Host: Is the number equal to or higher than 625.
- Host: Is the number equal to or higher than 687.
- Host: Is the number equal to or higher than 718.
- Host: Is the number equal to or higher than 702.
- Host: Is the number equal to or higher than 694.
- Host: Is the number equal to or higher than 698.
- Host: Is the number equal to or higher than 696.
- Host: The number is 676.
To emphasize what I meant by being able to scale, using the same series of queries to find the integer from 1 to 10000 will only require an additional three more attempts and we are talking about 9000 more records!
The opinions expressed in this post represent those of the individual author, Benny Wong, and not those of IEG or WNET.