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.