It’s a little tricky to define an algorithm, but informally we can use the term interchangeably with more well-known English words like recipe or procedure.
Definition: an algorithm is a finite sequence of unambiguous and effectively computable instructions that produce some intended result.
Let’s explore some of those terms in more detail:
An algorithm is independent of the language or notation in which it is specified. The binary search algorithm can be written in Python or Java or Ruby, but they’re all the same algorithm.
One notation sometimes used for algorithms is called pseudo-code (where pseudo of course means “false” or “fake”). Unlike real code in a programming language, pseudo-code cannot be executed directly by a computer. However, because it’s based on English (with a little mathematical notation), it’s easier for untrained humans to understand.
Below is an example of an algorithm, written in pseudo-code, that will compute the factorial of a given integer, N. (The factorial is the result of multiplying all the numbers between 1 and N, so factorial of 4 is 1×2×3×4 = 24.)
To understand this algorithm, we need to introduce the concept of a variable in programming. We use variables in mathematics too, but they’re a little different. In mathematics, a variable is a name given to a value, like x=5. In programming, a variable is a name given to a location in memory, which in turn can hold a value. The difference is that the value in the memory can be updated at a later time.
Let’s trace the algorithm. In step 1, we’re allowed to specify the value of N, as long as it is bigger than zero. This is a kind of input instruction. Let’s use 4, so that the algorithm computes the factorial of 4. In step 2, another variable K is named, but it’s initial value is 1. Here’s what that looks like:
Step 3 asks whether N=1. It does not, so we skip the rest of that instruction.
Step 4 updates a variable. We first compute the value of the expression: K×N = 1×4 = 4, and then we write that value to the box labeled K, replacing whatever was there before:
Step 5 updates the other variable. We first compute the value of the expression: N–1 = 4–1 = 3, and then we write that result to the box labeled N, replacing whatever was there before:
Step 6 says to go back to step 3. In step 3, N is still not 1, so we continue with the two updates again. This time, K×N = 4×3 = 12, and N–1 = 3–1 = 2:
N is still not 1, so we go through once more, producing these values for the two variables:
This time N=1, so in step 3 we output K and stop. By following this algorithm, we just computed the factorial of 4:
By starting the same algorithm with a different value of N, we could have computed any factorial.
Here’s an algorithm you can try tracing yourself.
I won’t tell you what this algorithm produces, but try it starting with these values for A and B:
A: 35 B: 21
Then try these:
A: 28 B: 12
And finally these:
A: 14 B: 33
Do you see the pattern? What does the algorithm compute?
One rich area of algorithms is sorting – putting things in some order, whether that’s alphabetical, numerical, chronological, or by size. There are many different sorting algorithms with different strengths and weaknesses. These videos introduce a few of them.
Whenever we talk about the “speed” of an algorithm, we have to consider the size of the input. In fact, we’re usually most concerned about how the size of the input impacts the running time, as that size increases. Maybe for sorting 8 elements, there isn’t much difference. But when we increase that to 50 or 1,000, dramatic differences may emerge.
Below is a graph comparing the number of comparisons for selection vs. merge sort, and also showing the lines N² and N·log₂(N), which are characterizations of these different approaches. You can see that the selection sort is somewhat less than N², however, they do grow large in the same awful way.
These rely on the
A[I] notation for arrays (composite, sequential variables) in the memory.
This is a variant of a selection sort. It is \(O(N^2)\).
1. Let A be an array of numbers 2. Set I to 0 3. If I+1 = size of A then stop 4. Set J to I+1 5. If J = size of A then Go to step 9. 6. If A[I] > A[J] then swap A[I] with A[J] 7. Set J to J+1 8. Go back to step 5. 9. Set I to I+1 10. Go back to step 3.
This isn’t any more efficient in the worst case, but the code can be simpler because it only needs one array index variable.
1. Let A be an array of numbers 2. Set I to 0 3. If I = size of A then stop 4. If I = 0 then Go to step 8 5. If A[I] ≥ A[I-1] then Go to step 8 6. Swap A[I] with A[I-1] 7. Set I to I-1 and Go back to step 3. 8. Set I to I+1 and Go back to step 3.