---
description: >-
  Big O time is the language and metric we use to describe the efficiency of the
  algorithms.
---

# Big O

{% embed url="https://www.bigocheatsheet.com" %}

* If your algorithm is in the form of "**do this, when you're all done, do that**" then you **add** the runtimes.
* If your algorithm is in the form of "**do this for each time you do that**" then you **multiply** the runtimes.

<table><thead><tr><th width="328" align="center">Add the Runtimes: O(A + B)</th><th align="center">Multipy the Runtimes: O(A * B)</th></tr></thead><tbody><tr><td align="center"><pre class="language-csharp"><code class="lang-csharp">foreach(int a in arrayA)
{
    Console.WriteLine(a);
}

foreach(int b in arrayB)
{
    Console.WriteLine(b);
}
</code></pre></td><td align="center"><pre class="language-csharp"><code class="lang-csharp">foreach(int a in arrayA)
{
    foreach(int b in arrayB)
    {
        Console.WriteLine(a + ", " + b);
    }
}
</code></pre><p></p></td></tr></tbody></table>

| `O(n!)` < `O(2^n)` < `O(n^2)` < `O(n log n)` < `O(n)` < `O(log n)` < `O(1)` |
| :-------------------------------------------------------------------------: |

{% embed url="https://flexiple.com/algorithms/big-o-notation-cheat-sheet/" %}

## Asymptotic Notations

<table data-view="cards"><thead><tr><th></th><th>Function</th><th>Description</th></tr></thead><tbody><tr><td><strong>Big-Oh</strong></td><td>f(x) = O(g(x))</td><td><code>g(x)</code> is an asymptotic upper bound for <code>f(x)</code></td></tr><tr><td><strong>Omega</strong></td><td>f(x) = Ω(g(x))</td><td><code>g(x)</code> is an asymptotic lower bound for <code>f(x)</code></td></tr><tr><td><strong>Theta</strong></td><td>f(x) = θ(g(x))</td><td><code>g(x)</code> is an asymptotic tight bound for <code>f(x)</code></td></tr><tr><td><strong>Small-o</strong></td><td>f(x) = o(g(x))</td><td><code>g(x)</code> is an asymptotic tight upper bound for <code>f(x)</code></td></tr><tr><td><strong>Small-omega</strong></td><td>f(x) = ω(g(x))</td><td><code>g(x)</code> is an asymptotic tight lower bound for <code>f(x)</code></td></tr></tbody></table>
