### What is an Alogirthm?

- How to systematically perform a task
- Sequence of steps (Varying degrees of detail)

Algorithms can be used to/for:

- Compute numerical functions
- Reorganize data
- Optimization

### How to optimise an algorithm? An example

##### Computing the gcd of two numbers (m,n)

The most obvious solution is to find all factors of the two numbers, see which ones are common and return the greatest one:

```
def gcd(m,n):
fm=[]
for i in range (1, m+1):
if(m%i)==0:
fm.append(i)
fn=[]
for j in range (1, n+1):
if(n%j)==0:
fn.append(j)
cf=[]
for f in fm:
if f in fn:
cf.append(f)
return (cf[-1])
```

Optimization 1: Both the factors can be found in the same loop

```
fm=[]
fn=[]
for i in range (1, max(m,n)+1): #assuming m>n
if(m%i)==0:
fm.append(i)
elif (n%i==0):
fn.append(i)
```

Optimization 2: We can reduce the loop to min (m,n) as the fcd cannot be greater than that. Also a common list can be used to save only the common divisors

```
fm=[]
fn=[]
for i in range (1, min(m,n)+1): #assuming m>n
if(m%i)==0 and (n%i==0):
cf.append(i)
```

Optimization 3: The list can be replaced by a single number and since we want gcd, instead of searching from lowest to highest, we should search from highest to lowest.

```
i= min(m,n)
while (m%i!=0 and n%i!=0):
i=i-1
return i
```

For further optimisation, you can read up on Euclids Algorithm

If you are stuck at any point or have any doubts, drop a message here