# Algorithm 1
###### tags: `Algorithm` `Teaching`
## Integer multiplication
a naive algorithm learned in elementary school:
Input: two n-digits number x and y
Output: product of x and y

$$
\qquad\text{ 1234 }\qquad
$$

$$
\quad\text{x}\,\,\,\text{ 5678 }\qquad
$$

---
$$
\quad\,\,\,\text{ 22712 }\qquad
$$

$$
\quad\,\text{ 17034* }\qquad
$$

$$
\;\,\,\text{ 11356** }\qquad
$$

$$
\;\,\,\text{ 5678*** }\qquad
$$

---
$$
\;\,\,\text{ 7006652 }\qquad
$$

how many times of multiplications have been operated?
Ans: $$1*n^2 $$
how many times of adding and multiplications have been operated?
Ans: can't be determined, the situation differs when we encounter a product caculation with two digits result.

The worst case(every multiplication leads to two-digit result)
Ans: $$ n^2+(n-1)*n+2*\sum_{i=1}^{n-1}i$$

The best case(no multiplication leads to two-digit result)
Ans:$$ n^2+2*\sum_{i=1}^{n-2}i+n-1$$

These are all polynomial of two degree of input size n.
What's the most influencial terms when input size -> infinity?

Can we implement this algorithm with for loop?(optionalXD)

## Ways to evaluate algorithms--Asymtotic Analysis
### gist:
1. Coarse enough to suppress architecture/language/compiler dependent details
2. Sharp enough to make useful comparisons between different algorithms, especially on large inputs

### Definition
#### 1.Big_Oh Notation
$$ \text{If T(n) is bounded above by a function f(n) for all sufficiently large inputs,}$$

$$ \text{then we can jump to the conclusion below:}\qquad\qquad\qquad\qquad\qquad\qquad\qquad$$

$$
T(n) = \text{Big_Oh}(f(n)) = O(f(n))
$$

Formal Definition: $$ T(n)=O(f(n)) <=> \exists c, n_0>0 \quad \forall c*f(n) \geq T(n)$$
#### 2.Omega Notation
$$ \text{If T(n) is bounded below by a function f(n) for all sufficiently large inputs,}$$

$$ \text{then we can jump to the conclusion below:}\qquad\qquad\qquad\qquad\qquad\qquad\qquad$$

$$
T(n) = \text{Omega}(f(n)) = \Omega(f(n))
$$

Formal Definition: $$ T(n)=\Omega (f(n)) <=> \exists c, n_0>0 \quad \forall c*f(n) \leq T(n)$$

#### 3.Theta_Oh Notation
If and only if
$$
T(n) = \text{Omega}(f(n)) = \Omega(f(n))
$$

$$
T(n) = \text{Big_Oh}(f(n)) = O(f(n))
$$
Then $$
T(n) = \text{Theta}(f(n)) = \Theta (f(n))
$$