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.

Logarithm

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.

Time Complexities

Big O notation Name Example
O(1) Constant Time  
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!)
O(2n) Exponential  

Feynman algorithm :wink:

  • Write down the problem.
  • Think real hard.
  • Write down the solution.

Dynamic programming

  • 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.