Introduction

Algorithm complexity is a measure of how long it would take an algorithm to complete given an input of size $n$. If an algorithm has to scale, it should complete the result within a finite and practical time bound even for large values of $n$. For this reason, complexity calculated asymptotically as $n$ 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?

Table of contents

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 $n \rightarrow \infin$, 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:

• $O(n)$ - functions whose growth is faster than $g$
• $\Omega(n)$ - functions whose growth is slower than $g$
• $\Theta(n)$ - functions whose growth is the same as $g$

For a given function $g(n)$ the notation $\Theta(g(n))$ denotes: $\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 \}$

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

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

Comparing Functions

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

$lim_{n \rightarrow \infin} \frac{f_n}{g_n}$

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: $f(n)=\Theta(g(n))$
• The limit is equal to zero. It means that the $g(n)$’s growth is faster than $f(n): f(n)=O(g(n))$
• The limit is equal to infinity. It means that the $g(n)$’s growth is slower than $f(n): f(n)=\Omega(g(n))$

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

$lim_{n \rightarrow \infin}\frac{f_n}{g_n}=\frac{f_n'}{g_n'}$

if functions have the following properties:

• $lim_{n \rightarrow \infin} = \frac{f_n}{g_n} = \frac{0}{0}$ or $lim_{n \rightarrow \infin} = \frac{f_n}{g_n} = \frac{\infin}{\infin}$
• $f(n)$ and $g(n)$ are differentiable
• $g(n)' \neq0$ when $n \rightarrow \infin$
• $\exist\space lim_{n \rightarrow \infin} \frac{f(n)}{g(n)}$

Example

Compare two functions $f(n)=n\log_2{n}$ and $g(n)=\log_2{n}^{2019}$

Proof:

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

Master Theorem

Defenition

Let us have a recurrence relation of the following form:

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

• If $c>\log_b{a}$, then $T(n)=\Theta(n)$
• If $c = \log_ba$, then $T(n)=\Theta(n^c \log_bn)$
• If $c < \log_ba$, then $T(n)=\Theta(n^{log_ba})$

Proof:

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

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

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

We get the tree cases:

1. If $c > \log_ba$, then $\sum(\frac{a}{b^c})^k$ is the sum of a decreasing geometric progression (where $\frac{a}{b^c} < 1$), which doesn’t depend on $n$. It means that the sum is just a constant. $T(n)=\Theta(n)$
2. If $c = \log_ba$, then $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)$
3. If $c < \log_ba$, then since the sum of a progression is asymptotically equivalent to its leading element, we have the following: $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}})$

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 $T(n)=T(\lceil \frac{n}{2} \rceil)+1$ is $O(\lg n)$

Proof:

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

Then,

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

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

Let’s see another example.

Show that the solution of $T(n)=T(n-1)+n$ is $O(n^2)$

Proof:

Assume, that $T(n) \le c*n^2$. Let’s substitute this inequality to a given recurrence.

Then,

$T(n) \le c*(n-1)^2+n =cn^2-2cn+c+n= \\\ cn^2+n(1-2c)+c \le \\\ cn^2$

The last step completes when $c \ge \frac{1}{2}$.

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 $T(n)=4T(\frac{n}{2} + 2)+n)$. Use the substitution method to verify your answer.

Proof:

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

The last level of depth $\log_2{n}$ contains $4^{\log_2{n}}=n^2$.

The total cost over all nodes:

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

Verifying by using substitution method:

Assume that $T(n) \leq c(n^2-dn)$. Let’s substitute this inequality to a given recurrence.

Then,

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

The last step completes when $cd-8c-1 \ge 0$.

Master Theorem

Use the master theorem to give tight asymptotic bounds for the following recurrences:

a. $T(n)=2T(\frac{n}{4})+1$ b. $T(n)=2T(\frac{n}{4})+\sqrt{n}$ c. $T(n)=2T(\frac{n}{4})+n$

Proof:

a. $a=2, b=4, c=1$. Hence, $T(n)=\Theta(\sqrt{n})$

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

c. $a=2,b=4,c=1$. Hence, $T(n)=\Theta(n)$