Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grokking algorithms 1 (Chapter 3. Recursion (The call stack with recursion…

- - - - All function calls go onto the call stack.
  - - - resolution: 1. tail recursion
        
        use a loop instead
- - - - O(log n), also known as log time. Example: Binary search.
      - O(n), also known as linear time. Example: Simple search.
      - O(n * log n). Example: A fast sorting algorithm, like quicksort (coming up in chapter 4).
      - O(n2). Example: A slow sorting algorithm, like selection sort (coming up in chapter 2).
      - O(n!). Example: A really slow algorithm, like the traveling salesperson (coming up next!).
- - - - Good
        
        Each item stores the address of the next item in the list
        
        your items can be anywhere in memory.
      - Bad:
        
        Suppose you want to read the last item in a linked list. You can’t just read it, because you don’t know what address it’s at
        
        Linked lists are great if you’re going to read all the items one at a time: you can read one item, follow the address to the next item, and so on. But if you’re going to keep jumping around, linked lists are terrible
    - - Bad
        
        One easy fix is to “hold seats”: even if you have only 3 items in your task list, you can ask the computer for 10 slots
        
        and then that memory will be wasted. You aren’t using it, but no one else can use it either.
        
        adding new items to an array can be a big pain. If you’re out of space and need to move to a new spot in memory every time, adding a new item will be really slow
      - Good
        
        Arrays are great if you want to read random elements, because you can look up any element in your array instantly
    - - run times for common operations on arrays and lists
      - The elements in an array are numbered. This numbering starts from 0, not 1.
    - - run times for common operations on arrays and linked lists.
    - - O(n*n)
        
        findSmallest:
        
        findSmallest with each element in array
- - - - Figure out the base case. This should be the simplest possible case.
        
        Divide or decrease your problem until it becomes the base case.
  - - - There’s another sorting algorithm called merge sort, which is
        O(n log n).
      - Quicksort is a tricky case. In the worst case, quicksort takes O(n2) time and In the average
        case, quicksort takes O(n log n) time
      - constant in runtime
        
        When you write Big O
        notation like O(n), it really means this. c*n
        
        c is some fixed amount of time that your algorithm takes. It’s called the constant
        
        You usually ignore that constant, because if two algorithms have
        different Big O times, the constant doesn’t matter
        
        Quicksort has a smaller constant than merge sort. So if they’re both O(n log n) time, quicksort is faster
        
        quicksort is faster in practice because it hits the average case way more often than the worst case
      - Average case vs. worst case
        
        The performance of quicksort heavily depends on the pivot you choose
        
        the best case is also the
        average case => quicksort will complete in O(n log n) time on average
        
        Quicksort is one of the fastest sorting algorithms out there, and it’s a very good example of D&C.