Algorithms Complexity: All You Should Know About It
Tags: algorithms, computerscience, complexity
Published: 2023-07-05 14:22:52

## Introduction

Algorithm complexity is a measure of how long it would take an algorithm to complete given an input of size {% katex inline %}n{% endkatex %}. If an algorithm has to scale, it should complete the result within a finite and practical time bound even for large values of {% katex inline %}n{% endkatex %}. For this reason, complexity calculated asymptotically as {% katex inline %}n{% endkatex %} approaches infinity.

In this article we are going to take a look at 

- Asymptotic notations
- How to compare two functions using limits?
- Master theorem
- How to solve recurrence relations?

---

## Asymptotic Notations

Calculation number of operations allows you to compare the efficiency of algorithms. As we’ve mentioned in the Introduction section, the analysis is carried out with the expectation of a sufficiently  large amount of processed data where {% katex inline %} n \rightarrow \infin {% endkatex %}, therefore, the growth rate is a key of importance, not the exact number of operations.

At this moment, we are ready to deep dive into details. Let’s define the function classes and consider asymptotic notations that describe the running time for a particular program or algorithm:

- {% katex inline %}O(n){% endkatex %} - functions whose growth is faster than {% katex inline %}g{% endkatex %}
- {% katex inline %}\Omega(n){% endkatex %} - functions whose growth is slower than {% katex inline %}g{% endkatex %}
- {% katex inline %}\Theta(n){% endkatex %} - functions whose growth is the same as {% katex inline %}g{% endkatex %}

For a given function {% katex inline %}g(n){% endkatex %} the notation {% katex inline %}\Theta(g(n)){% endkatex %} denotes: {% katex %}\Theta(g(n)) = \{ f(n): \exist \space  c_1 \ge \space 0 \space  \exists \space  c_2 \space  \ge \space  0 \space  \exist \space  n_0 \space \ge 0 \space  | \space 0 \le c_1g(n) \le f(n) c_2g(n), \forall n \ge n_0 \}{% endkatex %}

For a given function {% katex inline %}g(n){% endkatex %} the notation {% katex inline %}O(g(n)){% endkatex %} denotes: {% katex %}O(g(n)) = \{ f(n): \exist \space c \ge 0 \space | \space 0 \le f(n) \le cg(n), \forall n \ge n_0 \}{% endkatex %}

For a given function {% katex inline %}g(n){% endkatex %} the notation {% katex inline %}\Omega(g(n)){% endkatex %} denotes: {% katex %}\Omega(g(n)) = \{f(n): \exist \space c \ge 0 \space | \space 0 \le cg(n) \le f(n), \forall n \ge n_0\}{% endkatex %}


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wyo57blydrg5j3jelvg8.png)

---

## Comparing Functions

When we deal with complex algorithms, we are able to consider the limit of the ratio of the functions complexity:

{% katex %}lim_{n \rightarrow \infin} \frac{f_n}{g_n}{% endkatex %}

Based on the limit result, we can calculate the growth rate of the function:

- The limit is equal to constant and it’s not equal to zero. It means that the functions growth the same: {% katex inline %}f(n)=\Theta(g(n)){% endkatex %}
- The limit is equal to zero. It means that the {% katex inline %}g(n){% endkatex %}’s growth is faster than {% katex inline %}f(n): f(n)=O(g(n)){% endkatex %}
- The limit is equal to infinity. It means that the {% katex inline %}g(n){% endkatex %}’s growth is slower than {% katex inline %}f(n): f(n)=\Omega(g(n)){% endkatex %}

Also, we can consider a ratio of the derivatives of the function, like this:

{% katex %}lim_{n \rightarrow \infin}\frac{f_n}{g_n}=\frac{f_n'}{g_n'}{% endkatex %}

if functions have the following properties:

- {% katex inline %}lim_{n \rightarrow \infin} = \frac{f_n}{g_n} = \frac{0}{0} {% endkatex %} or {% katex inline %}lim_{n \rightarrow \infin} = \frac{f_n}{g_n} = \frac{\infin}{\infin} {% endkatex %}
- {% katex inline %}f(n){% endkatex %} and {% katex inline %}g(n){% endkatex %} are differentiable
- {% katex inline %}g(n)' \neq0{% endkatex %} when {% katex inline %}n \rightarrow \infin{% endkatex %}
- {% katex inline %}\exist\space lim_{n \rightarrow \infin} \frac{f(n)}{g(n)}{% endkatex %}

### Example

> Compare two functions {% katex inline %}f(n)=n\log_2{n}{% endkatex%} and {% katex inline %}g(n)=\log_2{n}^{2019}{% endkatex %}

**Proof**:

{% katex %}lim_{n \rightarrow \infin}\frac{f(n)}{g(n)}=lim_{n \rightarrow \infin}\frac{(n\log_2{n})'}{(\log_2{n^{2019}})'} \\\ =lim_{n \rightarrow \infin}\frac{log_2+1}{\frac{2019\log_{2}^{2018}n}{n}} \\\ =lim_{n \rightarrow \infin}\frac{n\log_2n+1}{2019*\log_{2}^{2018}n}=\infin \\\ \Rightarrow n\log_2{n} = \Omega(log_2{n^{2019}}){% endkatex %}

---

## Master Theorem

**Defenition**

Let us have a recurrence relation of the following form:

{% katex %}\begin{equation}T(n) =  \begin{cases}   a*T(\frac{n}{b})+O(n^c), &\text{n > 1} \\\   O(1) &\text{n = 1} \end{cases}\end{equation}{% endkatex %}

where {% katex inline%}a \in \mathbb{N}, b \in \mathbb{R}, b > 1, c \in \mathbb{R}^{+}{% endkatex %}. Then the solution of the given recurrence relation has the form:

- If {% katex inline %}c>\log_b{a}{% endkatex %}, then {% katex inline%}T(n)=\Theta(n){% endkatex%}
- If {% katex inline %}c = \log_ba{% endkatex%}, then {% katex inline%}T(n)=\Theta(n^c \log_bn){% endkatex %}
- If {% katex inline %}c < \log_ba{% endkatex%}, then {% katex inline%}T(n)=\Theta(n^{log_ba}){% endkatex %}

**Proof**:

Let’s consider the recursion tree. It has {% katex inline %}\log_bn{% endkatex %} levels where each {% katex inline %}k{% endkatex %}-level has {% katex inline%}a^k{% endkatex %} vertexes each of them costs {% katex inline %}(\frac{n}{b^k})^c{% endkatex %}. 

Let’s summarize the cost of the tree at all levels:

{% katex %}T(n)=\sum_{k=0}^{log_bn}a^k* \big( \frac{n}{b^k} \big)^c=n^c \sum_{k=0}^{log_bn} \big( \frac{a}{b^c} \big)^k{% endkatex %}

We get the tree cases:

1. If {% katex inline %}c > \log_ba{% endkatex %}, then {% katex inline %}\sum(\frac{a}{b^c})^k{% endkatex %} is the sum of a decreasing geometric progression (where {% katex inline %}\frac{a}{b^c} < 1{% endkatex %}), which doesn’t depend on {% katex inline %}n{% endkatex %}. It means that the sum is just a constant. {% katex %}T(n)=\Theta(n){% endkatex %}
2. If {% katex inline %}c = \log_ba{% endkatex %}, then {% katex %}T(n)=n^c\sum_{k=0}^{log_bn}(\frac{a}{b^c})^k=n^c\sum_{k=0}^{log_bn}1^k=\Theta(n^c\log_bn){% endkatex %}
3. If {% katex inline %}c < \log_ba{% endkatex %}, then since the sum of a progression is asymptotically equivalent to its leading element, we have the following: {% katex %}T(n)=n^c\sum_{k=0}^{\log_bn}(\frac{a}{b^c})^k=\Theta(n^c(\frac{a}{b^c})^{\log_{b}{n}})=\Theta(n^c*\frac{a^{\log_{b}{n}}}{n^c})=\Theta(a^{\log_{b}{n}})=\Theta(n^{\log_{b}{a}}){% endkatex %}

---

## Recurrence Relations

There are three main methods for solving recurrence relations: substitution method, recursion tree and master theorem. Let’s consider them.

### Substitution method

In order to solve a recurrence relation using the substitution method it's necessary to complete two steps:
- Make an assumption about the solution;
- Use the mathematical induction to prove the assumption’s correctness.

**Example**

> Show that the solution of {% katex inline %}T(n)=T(\lceil \frac{n}{2} \rceil)+1{% endkatex %} is {% katex inline%}O(\lg n){% endkatex %}

**Proof**:

Assume that {% katex inline %}T(n) \le c*\lg{(n-a)}{% endkatex %} (we used a definition of big-{% katex inline %}O{% endkatex %} from the Asymptotic Notations part), where {% katex inline %}a{% endkatex %} is a number which will be selected later. Now, we are ready to substitute it into initial recurrence.

Then,

{% katex %}T(n) \le c* \lg{(\lceil \frac{n}{2})\rceil - a} + 1 \le \\\ c*\lg{(n+1-2a)}+1-c*\lg{2} \le \\\ c*\lg{(n+1-2a)} \le \\\ c*\lg{(n-a)}{% endkatex %}

We proved that {% katex inline %}O(\lg{n}){% endkatex %} is a solution for the given relation when {% katex inline %}a \ge 1, \space c \ge 1{% endkatex %}.

---

Let’s see another example.

> Show that the solution of {% katex inline %}T(n)=T(n-1)+n{% endkatex %} is {% katex inline %}O(n^2){% endkatex %}

**Proof**:

Assume, that {% katex inline %}T(n) \le c*n^2{% endkatex %}. Let’s substitute this inequality to a given recurrence.

Then,

{% katex %}T(n) \le c*(n-1)^2+n =cn^2-2cn+c+n= \\\ cn^2+n(1-2c)+c \le \\\ cn^2{% endkatex %}

The last step completes when {% katex inline %}c \ge \frac{1}{2}{% endkatex %}.

---

### Recursion Tree

Another way to find a solution for relation recursion is using a Recursion Tree.

In this method, a recurrence relation is converted into recursive tree. Each node represents the cost incurred at various levels of recursion. To find the total cost, cost of all levels are summed up.

**Example**

> Use a recursion tree to determine a good asymptotic upper bound on the recurrence {% katex inline %}T(n)=4T(\frac{n}{2} + 2)+n){% endkatex %}. Use the substitution method to verify your answer.

**Proof**:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bpday65jez3449582jok.png)

The tree has {% katex inline %}\log_2{n}{% endkatex %} levels. The subproblem size for a node at depth {% katex inline %}i{% endkatex %} is {% katex inline %}\frac{n}{2^i}{% endkatex %}. The subproblem’s size reach {% katex inline %}1{% endkatex %} when {% katex inline %}\frac{n}{2^i}=1 \Rightarrow i=\log_2{n}{% endkatex %}.

The last level of depth {% katex inline %}\log_2{n}{% endkatex %} contains {% katex inline %}4^{\log_2{n}}=n^2{% endkatex %}.

The total cost over all nodes:

{% katex %}\sum_{i=0}^{\log{n-1}}(4^i*\frac{n}{2}+2)) + \Theta(n^2)= \\\ \sum_{i=0}^{\log{n-1}}(2^in+4^i*2) + \Theta(n^2) = \\\ \sum_{i=0}^{\log_{n-1}}2^in+\sum_{i=0}^{\log{n-1}}4^i*2+\Theta(n^2)= \\\ \frac{2^{\log{n}}-1}{2-1}n+\frac{2*4^{\log{n}}}{4-1}+\Theta(n^2)= \\\ (2^{\log{n}}-1)n+\frac{2}{3}(4^{\log{n}}-1)+\Theta(n^2) = \\\ (n-1)n+\frac{2}{3}(n^2-1)+\Theta(n^2)=\Theta(n^2){% endkatex %}

Verifying by using substitution method:

Assume that {% katex inline %}T(n) \leq c(n^2-dn){% endkatex %}. Let’s substitute this inequality to a given recurrence.

Then,

{% katex %}T(n) \leq4c((\frac{n}{2}+2)^2)-d(\frac{n}{2}+2)+n = \\\ 4c(\frac{n^2}{2}+2n+4-\frac{dn}{2}-2d)+n= \\\ cn^2+8cn+16c-2dnc-8dc+n= \\\ cn^2-cdn+8cn+16c-cdn-8cd+n= \\\ c(n^2-dn)-(cd-8c-1)n+(d-2)8c \leq \\\ c(n^2-dn){% endkatex %}

The last step completes when {% katex inline %}cd-8c-1 \ge 0{% endkatex %}.

--- 

### Master Theorem

> Use the master theorem to give tight asymptotic bounds for the following recurrences:
>
> a.) {% katex inline %}T(n)=2T(\frac{n}{4})+1{% endkatex %}
> b.) {% katex inline %}T(n)=2T(\frac{n}{4})+\sqrt{n}{% endkatex %}
> c.) {% katex inline %}T(n)=2T(\frac{n}{4})+n{% endkatex %}

**Proof**:

a.) {% katex inline %}a=2, b=4, c=1{% endkatex %}. Hence, {% katex inline %}T(n)=\Theta(\sqrt{n}){% endkatex %}

b.) {% katex inline %}a=2,b=4,c=\frac{1}{2}{% endkatex %}. Hence, {% katex inline %}T(n)=\Theta(\sqrt{n}\log_4{n}){% endkatex %}

c.) {% katex inline %}a=2,b=4,c=1{% endkatex %}. Hence, {% katex inline %}T(n)=\Theta(n){% endkatex %}