###### tags: `ADA 1.3` `Complexity`

# ADA 1.3 Algorithm Complexity & Problem Complexity

:::spoiler **Review Previous**
:::info
- $O$：
* Big Oh is define that an upper bound on an algorithm is most amount of time required.
- $Ω$：
* Big omega is define that an lower bound on an algorithm is least amount of time required.
- $Θ$：
* Big theat is define that the best of all the worst case times on an algoritm.
:::

## Tightness of the complexity
> Big Oh and Big omega is so closed on an algorithm.

:::info
So if the "$O(fn())$" is tight.
- = The "$Ω(f(n)$" is runs in worst case on that algorithm.
- = Time complexity of the algorithm is "$Θ(f(n))$".
:::

### Q: Can we say that Algorithm 1 is better than Algorithm 2 if bellow
- Algorithm 1 runs in $O(n)$ time
- Algorithm 2 runs in $O(n^2)$ time

:::spoiler **Answer**
:::warning
Not really, the algorithm 1 and 2 are not tight.
:::

## Ther Complexity of the Problem
> COP is defined different forom Complexity of the Algorithm.
:::info
- upper bound:
* There exists an $O(f(n))$_time algorithm that solves Problem P.
- lower bound:
* **Any** alforithm that solves Problem P requires "$Ω(f(n)$" time.
:::