> 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)$$.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://notes.theditor.xyz/time-complexity.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.