What is an algorithm
- An algorithm is a list of steps that shows how to perform a computational task.
- Converting an algorithm to code, makes it runnable on a computer.
- Algorithms come in many flavors.
SORTING
Arranging objects in order of size...
SEARCHING
Finding a book in the library...
GRAPHS
Calculating the best route for your road-trip...
CRYPTOGRAPHY
Encrypting data on the internet...
LEARNING
Teaching cars to drive themselves...
See "List of Algorithms." Wikipedia for more.
Example - Adding a set of numbers
Algorithm
Step 1: Create an array of numbers Step 2: Create a place to store the sum Step 3: Take next number from the array Step 4: Add it to the sum variable Repeat 3 and 4 until none remain Step 5: Print the sum
Code
number_list = [1,2,3,4,5]
sum = 0
for a_number in number_list:
sum = sum + a_number
print (sum)Performance of Algorithms
- Most algorithms work fine for small size of input.
- Good algorithms continue to work well even as we increase the size of input.
- Consider two algorithms to compute the sequence of factorials i.e. $1!$, $2!$ etc. up to $N!$.
Algorithm A
START
K! = 1 x ... x K
PRINT K!
END
$$\begin{align} & K! = 1\times2... \times K\\ &e.g.\\ &1! = 1 \\ &2! = 1 \times 2 \\ &3! = 1 \times 2 \times 3 \\ &4! = 1 \times 2 \times 3 \times 4\\ &...\end{align}$$ Starts from 1 every time
Algorithm B
START
K! = (K-1)! x K
PRINT K!
END
$$\begin{align} &K! = (K-1)! \times K\\ &e.g.\\ &1! = 1 \\ &2! = 1! \times 2\\ &3! = 2! \times 3\\ &4! = 3! \times 4\\ &...\end{align}$$ Starts with the previous result $(K-1)!$
- Observe how the number of steps to complete Algorithm A increases at a much faster rate than the number of steps for Algorithm B, with increasing values of N.
Order of Growth - Big O - $\mathcal{O}_n$
Performance of algorithms is characterized by their Order of Growth (or Big-O or \(\mathcal{O}_n\)), which indicates how completion time (or memory used) grows with increasing size of inputs.
- CONSTANT \((\mathcal{O}_1)\) algorithms complete the task in the same amout of time, no matter the size of input. These are the best, but almost impossible to find.
- LOGARITHMIC \((\mathcal{O}_{\log{}n})\) algorithms slow down at a very small rate with increasing size of input.
- LINEAR \((\mathcal{O}_n)\) algorithms take time directly proportional to the size of input.
- POLYNOMIAL \((\mathcal{O}_{n^k})\) algorithms take time proportional to a polynomial function (quadratic, cubic, etc.) of the size of input. These slow down significantly with increasing input size, but still complete within a reasonable time.
- EXPONENTIAL \((\mathcal{O}_{e^n})\) algorithms require increasingly larger amounts of time for even small increases in the size of input. Beyond a certain input size, these do not complete within a reasonable time at all and hence mostly unusable.
Read more about Algorithms at Sedgewick, Robert and Wayne, Kevin. Algorithms, 4th Edition.