# Logarithms - Interview Cake

04/01/2022 (Tuesday)

[Link to Interview Cake](https://www.interviewcake.com/article/python3/logarithms?course=fc1&section=algorithmic-thinking)

---

### In the interview -
* How many times must we double 1 before we get to n?
* How many times must we divide n in half in order to get bank down to 1?

---

### Logarithms in Binary search (ex. 1)

#### Procedure
1. Start with the middle number: is it bigger or smaller than our target numbers?
2. We’ve effectively divided the problem in half.
3. Repeat the same approach ( of starting in the middle) on the new half-size problem.
#### Time Complexity
* While loop
* How many times must we divide out original list size (n) in half until we get down to 1?
* O(log n) (base 2)

---

### Logarithms in Sorting (ex. 2)

#### Time Complexity
* O(n log n) (base 2) in general the best worst-case runtime

#### Merge Sort
* To divide the list in half, sort the two halve, and then merge the two sorted halves into one sorted whole.
* O(log n) - the number of times we have to cut n in half to get down to sublists of just 1 element (our base case).
* Additional O(n) - the time cost of merging all n items together each time we merge two sorted sublists.

---

### Logarithms in Binary Tree (ex. 3)

* The number of nodes in our perfect binary tree is always odd because the first level always has 1 node. (1 + 2 + 4 + 8 = 15)
* The number of nodes - formula (n + 1) / 2

#### Height (h)
* The number of times we have to double 1 to get to (n+1)/2
* h ≈ log[(n+1)/2] + 1 (base 2)
* The height is one more than the number of doublings.
* Simplified - h = log(n + 1) (base 2)

`In big O notation the base is considered a constant. So Folks usually don’t include it. People usually say O(log n), not O(log2 n).`