# 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="https://830969949-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJk6IGqxkOyDZ3FSL6p5y%2Fuploads%2FjhaFbZhwogfDXzASZNbE%2Fimage.png?alt=media&#x26;token=845f829f-20ab-49cc-ae2c-b1a31e0d3cba" alt="" width="563"><figcaption><p>Big Oh</p></figcaption></figure> <figure><img src="https://830969949-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJk6IGqxkOyDZ3FSL6p5y%2Fuploads%2FBpdWzOj9XPBVl81dKmBQ%2Fimage.png?alt=media&#x26;token=8d7398e4-7509-4989-af35-836163fb84cd" alt="" width="563"><figcaption><p>Theta</p></figcaption></figure> <figure><img src="https://830969949-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJk6IGqxkOyDZ3FSL6p5y%2Fuploads%2FvY6QuJoV0ERkUOsLnvMf%2Fimage.png?alt=media&#x26;token=ea9e8bd2-dc90-4cff-a0b0-724838a881f2" 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="https://830969949-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJk6IGqxkOyDZ3FSL6p5y%2Fuploads%2F2jl82Lwu3vRMW9LaP91H%2Fimage.png?alt=media&#x26;token=222e80e1-4d02-462f-b63b-0a7680f33abf" 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)$$.