---
# System prepended metadata

title: ADA 1.3 Algorithm Complexity & Problem Complexity
tags: [Complexity, ADA 1.3]

---

###### 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.
:::