Basic intro to Algorithms. Work in progress!
In other words, an algorithm is a computational procedure that takes in an input, processes it and then spits out an output.
There are certain properties an algorithm must have to be considered as valid.
There are many different algorithms for solving any specific type of problems. They differ in their approach, time to execute and space they need to perform the execution. For example, if we need to find a phone number in the phonebook, we could implement 2 different strategies.
Those two strategies are actually two valid algorithms. First one is called Linear search algorithm and the second one is Binary search algorithm.
Now, an important question is, which one is more efficient?
Unfortunately, there is no single correct answer. It depends on many factors. Say the phonebook contains 10,000 names. If the entry we are looking for is Aaron Anderson, the first algorithm will take only one or two steps to get the result. And the second algorithm will take about 14 steps. But if the name we are looking for is Zach Williams, it will probably take more than 9000 steps for the first algorithm, while it still takes around 14 steps for the second algorithm.
Considering those factors, we can come up with more of a general answer.
Linear search algorithm has a worst case scenario efficiency of n. Meaning if the input size is n = 1000, it will take maximum of 1000 steps to find the correct entry or discover that it is not there.
Binary search algorithm has the worst case scenario efficiency of .
Quick Logarithms refresher
- Definition: is equivalent to Example: because
- Definition: is the same as Example: that is
- means that for , , because
Another critical part of assessing the efficiency of an algorithm is to decide what will be called a step. In the phonebook example above, we considered a comparison as a step. We look at an entry and compare it with the key we are looking for. That is one step. A step must be the most time consuming action in the algorithm and other actions are ignored. For example, when determining the worst case scenario, and are the same. Because when the value of is tremendous, +97 and 2X become not important.
Also, we should only compare algorithms when the input size n is large enough. For small inputs, it does not really make a difference which algorithm to use.
To summarize, we need to take the following points into consideration when determining the efficiency of an algorithm:
Let us look at an example to solidify the rules we discussed.
Example 1. Perform a worst case scenario computation for the following algorithm.
Find the maximum value from a list of numbers
Input: A list of numbers Output: max()
1: max_value 2: next 2 3: while next n.length do 4: if max_value 5: max 6: end if 7: next next + 1 8: end while 9: output max_value
Solution In the algorithm, the size of the problem n is equal to the list of the numbers given as a parameter. And comparing the next value to the max value can be counted as one step. We are making two comparisons with each of the items in the list. So this algorithm has the efficiency of 2n.
Let's clarify some points here. First of all, we only need to compare the last items in the list. But even then we can say that we do two comparisons for each item. Because being off by a few numbers does not really matter in this specific case. Second of all, where is the second comparison? I only see one for each item in the list. Well, the first comparison is on line 3. We check to see if the value of next is less than the length of n. The second comparison is on line 4. When we compare the value of the next item in the list with the max_value. Last but not least, we need to drop the constants. Efficiency of 2N is actually just N because we are only interested in the rate of incraese when dealing with efficiency of algorithms.
Here is the javascript version of the algorithm given above.
function max(input) {
/* input is an array of numbers */
let max_value = input[0];
let next = 1;
while (next <= input.length) {
if (max_value < input[next]) {
max_value = input[next];
}
next++;
}
return max_value;
}