## 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.

See "List of Algorithms." Wikipedia for more.

## 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.