> For the complete documentation index, see [llms.txt](https://kdongs.gitbook.io/kdocs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kdongs.gitbook.io/kdocs/complexity/asymptotic-behavior.md).

# Asymptotic Behavior

## About

Describes the effort given an input of $$N$$ size.

* This is used to analyze an algorithm efficiency as your input goes to $$\infty$$. *(Growth Rate)*
* How drastically the time grows as the input grows.

**In the real world**

*Memory growth is not computationally free. In languages like* `Go` *or* `Javascript` *you pay even heavier penalties because the memory can be kept around, grows faster, and causes complete halts in the program for cleanup.*

*But these things are not considered for Complexity calculations.*

**Rules:**

* Ignore constants:
  * Constants are any value that do not scale with the input.
  * Constant values are ignored.
  * Ex.: , the $$2$$ is ignored.
* Ignore lower order terms:
  * Ex.: $$O(N) + 10$$, the $$10$$ is ignored.
  * Ex.: $$O(N^2) + 10N$$, $$10N$$ is also ignored.

## Big-O $$(O)$$

{% hint style="info" %}
Describes the upper-bound, or the **worst case** for a given function.
{% endhint %}

{% hint style="danger" %}
In the code evaluation, you must always consider the costliest paths.
{% endhint %}

Also Big-O states that a given function $$f()$$ will be of a complexity of **NO MORE THAN** some asymptotic notation.

**It can be less.**

<figure><img src="https://1676597367-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F2mESLFU6jPzdl3vMCznc%2Fuploads%2FEm5XosfYGJezDu77ewFg%2Fcomplexity-chart.png?alt=media&amp;token=be09a213-5c79-488f-8e88-1033d008a5df" alt=""><figcaption></figcaption></figure>

### O(1)

{% hint style="success" %}
**Constant** - Excellent
{% endhint %}

Given a input $$N$$, the cost will always be constant $$(1)$$, no matter how big $$N$$ is.

### O(log N)

{% hint style="success" %}
**Logarithm** - Excellent
{% endhint %}

{% hint style="info" %}
It is when the algorithm has a behavior close to "Divide to Conquer". Meaning you just keep dividing until there is just 1 element left. *(**You cannot scan*****&#x20;`linear search`&#x20;*****the divided parts**)*
{% endhint %}

When you divide the data and analyses just part that needs.

It is much closer to `Constant Time` than `Linear`.

{% hint style="info" %}
**The larger the input the more constant it gets.**
{% endhint %}

Ex.:

> Search for a name in a list.\
> You don't have to look the entire list, but start from the names where the first letter is the same as the one you want.\
> Ex.: Binary Search.

### O(N)

{% hint style="success" %}
**Linear** - Good
{% endhint %}

The cost is linearly proportional as the input.

*Recursions end up being just like regular loops.*

### O(N log N)

{% hint style="success" %}
**Linearithmic ou Quasilinear** - Bad
{% endhint %}

As if it were $$log\ N$$ executed $$N$$ times.

{% hint style="info" %}
It can be when you keep dividing your input at each step, like in $$O(log N)$$, **but you do scan the part each time**.
{% endhint %}

Ex.:

> Some search algorithms like Merge Sort.

### O(N²)

{% hint style="success" %}
**Quadratic** - Horrible
{% endhint %}

The cost rises quadratically as $$N$$.

Ex.:

> Nested loops

### O(2^N)

{% hint style="success" %}
**Exponential** - Horrible
{% endhint %}

The cost rises exponentially as $$N$$.

Ex.:

> Hanoi Tower.

### O(N!)

{% hint style="success" %}
**Factorial** - Horrible
{% endhint %}

Ex.:

> Travelling Salesman Problem.

## Big-Omega $$(\Omega)$$

{% hint style="info" %}
Describes the lower-bounds, or the **best case scenarios**.
{% endhint %}

Also Omega states that a given function $$f()$$ will be of a complexity of **AT LEAST** some asymptotic notation.

**It can be more.**

## Theta $$(\Theta)$$

Denotes the asymptotically tight bound on the growth rate of runtime of an algorithm.

This means that it takes exactly the asymptotic time:

* No more than $$O()$$.
* And no less than $$\Omega()$$.

$$\Omega() = \Theta() = O()$$