# Complexity or Asymptotic Behavior

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://2084165766-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FDX21luuozz1jipR3n2Kp%2Fuploads%2FMMVFvIpkaRuhwHLCEJXa%2Fcomplexity-chart.png?alt=media&#x26;token=4ec3f087-a5a7-42d7-9e38-9ac7f0ad7080" 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()$$
