Summary of selected chapters:

# Chapter 3

• $$f(n)=\Theta(g(n))$$ is a sandwich bound ( = )
• $$f(n)=O(g(n))$$ is a tight upperbound ( ≤ )
• $$f(n)=\Omega(g(n))$$ is a tight lowerbound ( ≥ )
• $$f(n)=o(g(n))$$ is a loose upperbound ( $$<$$ )
• $$f(n)=\omega(g(n))$$ is a loose lowerbound ( $$>$$ )

e.g. $$2n^2 = O(n^2)$$ but $$2n^2 \neq o(n^2)$$, $$n=o(n^2)$$ and $$n=O(n^2)$$, $$f(n)=\omega(g(n))\;\implies\;\Omega(g(n))$$

# Chapter 4

How to prove an recurrence formula?

• Substitution method: Guess the anser and proof it by mathematical induction
• Recursion tree: Build a tree with the nodes denoting the fixed cost and children denotes recurred functions. Then sum up all nodes after the tree is complete
• Using master theorem: For solving $$T(n)=aT(n/b)+f(n)$$

Master theorem: Let $$T(n)=aT(n/b)+f(n)$$ where $$a\ge 1$$ and $$b>1$$. The term $$n/b$$ in the formula can also be $$\textrm{ceil}(n/b)$$ and $$\textrm{floor}(n/b)$$. $$T(n)$$ is defined on non-negative integers. Then,

• If $$f(n)=O(n^{\log_b a-\epsilon})\ \exists\epsilon>0$$ then $$T(n)=\Theta(n^{\log_b a})$$
• If $$f(n)=\Theta(n^{\log_b a})$$ then $$T(n)=O(n^{\log_b a}\log_2 n)$$
• If $$f(n)=\Omega(n^{\log_b a+\epsilon})\ \exists\epsilon>0$$ and $$af(n/b)\le cf(n)\ \exists c<1\ \forall n>n_0$$ then $$T(n)=\Theta(f(n))$$

Interpretation of the master theorem: The recursion $$T(n)=aT(n/b)$$ gives $$\Theta(n^{\log_b a})$$. Thus if the recursion part dominates, the solution is this. But if the $$f(n)$$ part dominates, the result is as $$f(n)$$. If both parts weigh equally, both appears in the result. The proof is in section 4.4.

# Chapter 5

## Calculating probability using indicator variable

Let $$I_A$$ be an indicator (0 or 1) of event $$A$$ happened. Then the expected value of $$I_A$$ equals to the probability of $$A$$.

Example: To interview n random persion in sequential order, how many times we see the best-candidate-so-far? If we are interviewing the $$k$$-th persion, it is the best so far in probability of $$1/k$$. Defining $$X_k$$ to be the indicator of best-so-far, the count $$N$$ satisfies $$E(N)=\sum_k E(X_k)=\sum_k 1/k = O(\log n)$$. Indeed, $$E(N)=\ln n + O(1)$$.

In $$n$$ bins and $$m$$ balls, each ball falls in a bin randomly. Find the probability that no bin contains ≥2 balls.

For $$m=2$$, the probability is $$1/n$$ and the probability of not is $$1-1/n$$. For $$m=3$$, the probability of not is $$1\times(1-\frac{1}{n})\times(1-\frac{2}{n})$$ (first ball $$\times$$ second ball $$\times$$ third ball)

Thus for general $$m$$ ($$m\le n$$), it is $$\prod_{k=1}^{m-1} (1-\frac{k}{n})$$. In case $$m<<n$$, we have $$e^x = 1+ x + x^2/2! + \cdots \approx 1+x$$ thus $$\prod_{k=1}^{m-1}(1-\frac{k}{n})=\prod_{k=1}^{m-1}e^{-k/n}=\exp(-\frac{m(m-1)}{2n})$$

For probability of $$<0.5$$, what is the marginal $$m$$?
Solving $$\exp(-\frac{m(m-1)}{2n}) \le \frac{1}{2}$$ gives $$(m-1)m\ge 2n ln2$$, then

## Bibliographic data

@book{
title = "Introduction to Algorithms",
edition = "2nd",
author = "Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein",
publisher = "MIT Press",
year = "2002",
}