Book Club: Grokking Algorithms. 3: Introduction to algorithms, Selection sort, and Recursion
Tags: discuss, books, algorithms, bookclub
Published: 2023-05-26 14:25:37

---
title: Book Club: Grokking Algorithms. 3: Introduction to algorithms, Selection sort, and Recursion
published: true
description: Book Club discussion for Grokking Algorithms by Aditya Y. Bhargava
tags: [discuss, books, algorithms, bookclub]
series: ["book club Grokking Algorithms"]
---

#### **Grokking Algorithms** An _illustrated_ guide for programmers and other curious people, by Aditya Y. Bhargava

-----

## Chapters 1 to 3: Introduction to algorithms, Selection sort, and Recursion

If you read any of these chapters, please go ahead and discuss what you thought in the comments! I really liked the explanation of Big O notation, I think it's perceived as something very complex which it doesn't have to be - perhaps because it's not used practically very often as a developer?

:memo: you can read my notes below.

:calendar: The next post will be on chapters 4 - 6. I'll aim for June or July 2023.
If you're on [Storygraph](https://app.thestorygraph.com/profile/ruthmoog) and want to join me, say hi and I'll start a Buddy Read.

-----

### Introduction to algorithms

This chapter nicely introduces Big O notation, which is lauded as a thing everyone needs to know for tech interviews... but it's simply a way of indicating how fast an algorithm is.

We cover Binary Search first which is a fundamental algorithm that chops your sorted set into two parts (the bi in binary) and discards the half that doesn't meet your criteria.

Algorithm speed is measured in growth: 
- how quickly the runtime increases with the size of input

Runtime is expressed in Big O notation:
- a measure of how fast an algorithm is
- establishes the worst-case scenario (e.g. if the name you're looking for in the phone book was 'Z' not 'A')

Here's the [Khan Academy video about logarithms](https://www.youtube.com/watch?v=Z5myJ8dg_rM&ab_channel=KhanAcademy), mentioned on page 7.

### Selection sort

This chapter compares computer memory to a set up draws, and introduces arrays and lists as ways to sore multiple elements in memory. Arrays being a collection of draws next to each other, and linked lists being a treasure hunt for each next item.

Arrays are great for fast reading, whereas linked lists are great for fast inserts and deletes.

Array `insert` is proportional to the size needed in memory to move the _entire array_.
List `read` is proportional to the length of the list to iterate through, to find _all_ addresses in memory

Linked lists can only allow sequential access, arrays can do both sequential and random access.

### Recursion

The recursion chapter has a lot of practical examples!

When a function calls itself, thats recursion.
Here's an example I did in Java, there's always a base case and a recursive case!

```java
    /**
     * counts down to 1
     * @param i number to start counting down from
     */
    public static void countdown(int i) {
        System.out.println(i);
        if (i <= 1) { // base case
            return;
        } else { // recursive case
            countdown(i-1);
        }
    }
```

With recursion the call stack can get huge which takes up a lot of memory (too much and you get a stack overflow). Stacks have two operations, `push`, and my favourite, `pop`. All function calls go on the stack.


![Push and Pop](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/psxx3kstgao9cyf96ypk.png)
<figcaption>Push and Pop, copyright Manning Publications, drawn by adit.io</figcaption>

-----