Maths is fun. Lot of concepts that we learn during academia gets rusty over time. I thought of giving it a revival. Recently I read the book “Grokking Algorithms”. I tried to capture the notes in the following post.
How many of one number do we multiply to get another number?
- How many two’s do we multiply to get 8? log2(8) = 3
- Common Logarithm (Base 10) log10(n) - It is how many times we need to use 10 in a multiplication, to get our desired number.
- Logs are flips of exponentials
Big O notation
- Big O notation tells you how fast an algorithm is.
- It doesn’t tell the algorithm speed in seconds or milliseconds.
- It rather tells you how the algorithm grows in number of operations.
- It focuses on worst case scenario.
- O(log n) is faster than O(n), but it gets a lot faster once the list of items you’re searching through grows.
|Big O notation||Name||Example|
|O(log n)||Log time||Binary search|
|O(n)||Linear time||Simple search|
|O(n * log n)||Linearithmic||A fast sorting algorithm, like quicksort, merge sort|
|O(n2)||Quadratic||A slow sorting algorithm, like selection sort, bubble sort|
|O(n3)||Cubic||A slow sorting algorithm, like selection sort|
|O(n!)||Factorial||A really slow algorithm, like the traveling salesperson (coming up next!)|
Feynman algorithm :wink:
- Write down the problem.
- Think real hard.
- Write down the solution.
- Dynamic programming is useful when you’re trying to optimize something given a constraint.
- Every dynamic-programming solution involves a grid.
- The values in the cells are usually what you’re trying to optimize.
- Each cell is a subproblem, so think about how you can divide your problem into subproblems.