> For the complete documentation index, see [llms.txt](https://notes.theditor.xyz/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://notes.theditor.xyz/time-complexity.md).

# Time Complexity

## Asymptotic Notations

1. Big oh - $$O$$ - Upper bound - $$f(n) = O(g(n))$$ iff $$f(n) \le c \cdot g(n)$$ - Any higher/equal order function than average case
2. Big omega - $$\Omega$$ - Lower bound - $$f(n) = \Omega(g(n))$$ iff $$f(n) \ge c \cdot g(n)$$ - Any lower/equal order function than average case
3. Theta - $$\theta$$ - Average bound - $$f(n) = \theta(g(n))$$ iff $$c\_1 \cdot g(n)\le f(n) \le c\_2 \cdot g(n)$$

{% hint style="info" %}
Since $$\theta$$ gives most accurate bound of a function, it is preferred over $$O$$ and $$\Omega$$ which are boundless.

Note: These aren't linked with best case or worst case scenarios, these are just notations. Worst case and best case can be shown using any of these notations.
{% endhint %}

<div data-full-width="true"><figure><img src="/files/vIAKHiYzyALUEryI0wFf" alt="" width="563"><figcaption><p>Big Oh</p></figcaption></figure> <figure><img src="/files/VIdcJawrLqyVHflEuD2p" alt="" width="563"><figcaption><p>Theta</p></figcaption></figure> <figure><img src="/files/Tv8NdwZygZOWM2RlrXsl" alt="" width="563"><figcaption><p>Big Omega</p></figcaption></figure></div>

### Properties

<table><thead><tr><th width="294">Property</th><th width="149" data-type="checkbox">O</th><th width="171" data-type="checkbox">Ω</th><th data-type="checkbox">θ</th></tr></thead><tbody><tr><td>Reflexive</td><td>true</td><td>true</td><td>true</td></tr><tr><td>Transitive</td><td>true</td><td>true</td><td>true</td></tr><tr><td>Symmetric</td><td>false</td><td>false</td><td>true</td></tr><tr><td>Transpose Symmetric</td><td>true</td><td>true</td><td>false</td></tr></tbody></table>

{% hint style="info" %}
Transpose Symmetric is if $$f(n) = O(g(n))$$ then $$g(n) = \Omega(f(n))$$
{% endhint %}

## Comparing Functions

* Functions can be directly compared, however, two functions can be of same complexity (asymptotically equal) even if their constants are unequal. Natively constants **do not** hold significance in comparing functions.
* If two functions cannot be directly compared (i.e. powers exist), logarithms can be used to compare such functions, however, when taking logarithm - any constants generated by application of logarithm **DO HOLD** significance and hence after application of logarithm, two functions cannot be asymptotically equal if they have differing constant coefficients.

{% hint style="info" %}
Examples

1. Functions $$2n^{\sqrt n}$$ and $$3n^{\sqrt n}$$ are asymptotically equal.
2. Functions $$2^{2n^{\sqrt n}}$$ and $$2^{3n^{\sqrt n}}$$ are **NOT** asymptotically equal, even though on application of logarithm it produces the same functions as in Example 1.
   {% endhint %}

## Big O Cheat Sheet

<figure><img src="/files/eqKYAl3mglXUQFXdRmGV" alt=""><figcaption><p>bigocheatsheet.com</p></figcaption></figure>

## Calculating complexity

1 sec = $$10^8$$ operations (approx.)

#### Example

Time constraint: 20 seconds

$$0 < n \le 2 \times 10^5$$

Here to find out the time complexity, consider $$n^2 = 4 \times 10^{10}$$ which would equal to `400 seconds`. Hence, time complexity here should be less than $$O(n^2)$$.