Title

# analyzing algorithms
toddpla.github.io/analysing-algorithms

---
class: center
# contents
----

1. why?
1. nth notation
1. big O
1. examples

---
class: middle

### algorithm:
### a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.

---

???
Problems have many solutions.  
  
With small inputs the difference in performance of these algorithms may be negligible.  
   
However, if we double the input or times it by 1000 or times it by infinity then we want to know how the performance will be effected.
--
##### scaling
--

#### scaling
--

### scaling
--

## scaling
--

# scaling

---
class: center
## nth notation
----

https://en.wikipedia.org/wiki/Time_complexity

???
n is a function n

---
.center[
## some math 🤓
]

----

## exponential

<h2 style="width: 100px; position: absolute;">logarithmic</h2>

--

<h2 style="width: 100px; position: absolute;">factorial</h2>

???
52! ways to shuffle a pack of cards = 8.06... × 10<sup>67</sup>  
60! atoms in the universe = 8.32... × 10<sup>81</sup>

---
class: center
## some numbers 🥳 
----

<table>
    <tr><th>input</th><th>n!</th><th>2<sup>n</sup></th><th>n<sup>2</sup></th><th>n</th><th>log<sub>2</sub>(n)</th><th>1</th></tr>
    <tr><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td></tr>
    <tr><td>2</td><td>2</td><td>4</td><td>2</td><td>2</td><td>1</td><td>1</td></tr>
    <tr><td>3</td><td>6</td><td>8</td><td>9</td><td>3</td><td>1.58</td><td>1</td></tr>
    <tr><td>4</td><td>24</td><td>16</td><td>16</td><td>4</td><td>2</td><td>1</td></tr>
    <tr><td>5</td><td>120</td><td>32</td><td>25</td><td>5</td><td>2.32</td><td>1</td></tr>
    <tr><td>6</td><td>720</td><td>64</td><td>36</td><td>6</td><td>2.58</td><td>1</td></tr>
    <tr><td>7</td><td>5040</td><td>128</td><td>49</td><td>7</td><td>2.81</td><td>1</td></tr>
    <tr><td>8</td><td>40320</td><td>256</td><td>64</td><td>8</td><td>3</td><td>1</td></tr>
    <tr><td>9</td><td>362880</td><td>512</td><td>81</td><td>9</td><td>3.16</td><td>1</td></tr>
    <tr><td>10</td><td>3628800</td><td>1024</td><td>100</td><td>10</td><td>3.32</td><td>1</td></tr>
</table>

---
class: center
## n = 1
----
--

---
class: center
## n = n
----
--

.left[```js
function printAllItemsInSomeArrayOnce(someArray) {
    for (let i = 0; i < someArray.length; i++) {
        console.log(someArray[i]);
    }
}
```]

---
class: center
## n = n<sup>2</sup>
----
--

.left[```js
function printAllCombinationsInAnArray(someArray) {
    for (let i = 0; i < someArray.length; i++) {
        for (let j = 0; j < someArray.length; j++) {
            console.log(someArray[i], someArray[j]);
        }
    }
}
```]
--

---
class: center

## n = ???
----
--

.left[```js
function findInSortedArray(sortedArray, someNumber) {
    for (let i = 0; i < sortedArray.length; i++) {
        if (sortedArray[i] === someNumber) return i;
    }
}
```]
--
.left[```js
const sortedArray = [6, 11, 13, 21, 26, 42, 64, 78, 82, 98];
```]
--
.left[```js
console.log(findInSortedArray(sortedArray, 6));
//--> executions: 1
```]
--
.left[```js
console.log(findInSortedArray(sortedArray, 21));
//--> executions: 4
```]
--
.left[```js
console.log(findInSortedArray(sortedArray, 82));
//--> executions: 9
```]

---
class: center, middle, dark
# o, O, Θ, Ω and ω

---

## Represent boundaries

<table>
    <tr>
        <td>little omicron</td>
        <td>o(n)</td>
        <td>faster</td>
    </tr>
    <tr style="background-color: black; color: white">
        <td><strong>big omicron</strong></td>
        <td><strong>O(n)</strong></td>
        <td>faster or equal</td>
    </tr>
    <tr>
        <td>big theta</td>
        <td>Θ(n)</td>
        <td>equal to</td>
    </tr>
    <tr>
        <td>big omega</td>
        <td>Ω(n)</td>
        <td>slower or equal</td>
    </tr>
    <tr>
        <td>little omega</td>
        <td>ω(n)</td>
        <td>slower</td>
    </tr>
</table>
???
Go back through each example and demonstrate the big O notation

---
class: center
## n = log<sub>2</sub>(n) 🤯

----

.left[
```js
function logarithmicSearch(sortedArray, item) {
    let left = 0;
    let right = sortedArray.length - 1;
    let middle;
    while (left <= right) {
        middle = Math.floor((left + right) / 2);
        if (sortedArray[middle] < item) left = middle + 1;
        else if (sortedArray[middle] > item) right = middle - 1;
        else return middle;
    }
}
```
]

---
## summary
1. we found out that analysing algorithms is good for predicting how an algorithm will scale with increasing input
1. we looked at some commonly used nth notations including 1, n, n<sup>2</sup>, n! and log<sub>2</sub>(n) that helped us describe the different ways in which an algorithm might scale
1. we used the big O notation for helping us describe the upper bound of an algorithm
1. we compared two search algorithms that scaled differently

---
class: center, middle

![](assets/images/badger.gif)  
# thanks