> For the complete documentation index, see [llms.txt](https://wiki.hanzheteng.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wiki.hanzheteng.com/algorithm/cs/analysis.md).

# Analysis

## Asymptotic Notations

* formal definition: $$f(n) = O(g(n))$$if there exists positive constants$$c$$and$$n\_0$$such that $$0 \le f(n) \le cg(n)$$for all $$n \ge n\_0$$. 
* $$\lim\_{n\to\infty} \frac{f(n)}{g(n)} \le constant$$ 

|         notation        | (literal) meaning |        example 1       |         example 2        |         example 3        |
| :---------------------: | :---------------: | :--------------------: | :----------------------: | :----------------------: |
|    $$f(n) = O(g(n))$$   | $$f(n) \le g(n)$$ |     $$n = O(n^2)$$     |     $$n^2 = O(n^2)$$     |    $$n^3 \neq O(n^2)$$   |
| $$f(n) = \Omega(g(n))$$ | $$f(n) \ge g(n)$$ | $$n \neq \Omega(n^2)$$ |   $$n^2 = \Omega(n^2)$$  | $$n^3 \neq \Omega(n^2)$$ |
| $$f(n) = \Theta(g(n))$$ |  $$f(n) = g(n)$$  | $$n \neq \Theta(n^2)$$ |   $$n^2 = \Theta(n^2)$$  | $$n^3 \neq \Theta(n^2)$$ |
|    $$f(n) = o(g(n))$$   |  $$f(n) < g(n)$$  |     $$n = o(n^2)$$     |    $$n^2 \neq o(n^2)$$   |    $$n^3 \neq o(n^2)$$   |
| $$f(n) = \omega(g(n))$$ |  $$f(n) > g(n)$$  | $$n \neq \omega(n^2)$$ | $$n^2 \neq \omega(n^2)$$ |   $$n^3 = \omega(n^2)$$  |

more reference: [Orders of common functions](< https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions>)

## Randomized Algorithms and Average-case Analysis

#### Examples

* the hiring problem: in average O(log(n)) instead of O(n)
* quicksort: the cost is O(n log(n)) on average
* hash table: expected O(1)
* Rabin-Karp: sub-string matching

## Amortized Analysis

Though the algorithm is deterministic, the cost of each step may be different

#### Examples

* Binary Counter and Piggy Bank
  * pay only when a bit changes from 0 to 1
* Hash Table
  * load factor better to be 1/2
  * need to resize when full
    * worst case cost: O(n)
    * amortized to O(1)
* Union-find with path-compression: O(log\* n) per union or per find
* Weight balanced tree with rebuilding
  * O(log n) cost per insertion
    * O(1) cost for rebalance per insertion
    * O(log n) cost for insertion itself

#### Three ways for amortized analysis

* Direct: count the total cost from an empty state all the way to the n-th operation O(f(n))
  * then the total cost of each operation is $$O(\frac{f(n)}{n})$$&#x20;
* Piggy bank: pay O(k) “dollars” per operation
  * show that even though some of the operations are more expensive, the total cost of all n elements are no more than O(nk)
* Potential function: design a potential function$$\Phi (s)$$for a certain state, and analyze the change of$$\Phi$$, from which we can derive the amortized cost

### &#xD;