Understanding time complexity on simple examples - Part 4

calendarNov 20, 2023 · 8 min read  ·
Share on: linkedincopy

In this post, we will provide another concrete illustration of the concepts discussed by comparing various algorithms for calculating linear recurrence sequences. We will once again demonstrate that certain methods are significantly more efficient than others.

Let $a,b,c,d \in \mathbb{R}$ and $(u_{n})$ be a sequence such that $u_{0}=a$, $u_{1}=b$ and $u_{n}=cu_{n-1}+du_{n-2}$ for all $n \ge 2$. We aim to determine an estimation of the execution time for computing the $n$-th term of this sequence.

We will define an IComputeSequence interface that all algorithms will implement.

1public interface IComputeSequence
2{
3    double ComputeSequence(int n);
4}

Algorithm 1

The first algorithm is quite naive and mirrors the recurrence formula.

1public class NaiveComputeSequence : IComputeSequence
2{
3    public double ComputeSequence(double a, double b, double c, double d, int n)
4    {
5        if (n == 0) return a;
6        if (n == 1) return b;
7        return c * ComputeSequence(a, b, c, d, n-1) + d * ComputeSequence(a, b, c, d, n-2);
8    }
9}

Analysis of the algorithm

We denote $T(n)$ as the number of additions and multiplications performed during the execution of the program.

$$T(n) = \begin{cases} 0 &\text{if } n=0 \text{ or } n=1 \\ 3+T(n-1)+T(n-2) &\text{if } n \ge 2 \end{cases}$$

Consider, for all $n \ge 0$, $v_{n}=T(n)+3$ so that $v_{0}=3$, $v_{1}=3$ and $v_{n}=v_{n-1}+v_{n-2}$ for all $n \ge 2$. We end up with a straightforward Fibonacci sequence, and with no difficulty, we find that $v_{n} \thicksim \lambda(\dfrac{1+\sqrt 5}{2})^n$ for all $n \ge 0$ where $\lambda \in \mathbb{R}$ and whose value is unimportant here.

$$\boxed{T(n)=O(2^n)}$$

Hence, this algorithm is impractical for large values of $n$, necessitating the search for an alternative approach better suited to address the problem.

Algorithm 2

The issue with this algorithm is that it fails to store intermediary results, resulting in the repetition of computations for the same formula. A more sophisticated approach can mitigate this naivety and potentially yield improved execution times.

 1public class LessNaiveComputeSequence : IComputeSequence
 2{
 3    public double ComputeSequence(double a, double b, double c, double d, int n)
 4    {
 5        var tmp1 = a; var tmp2 = b;
 6        var tmp3 = c * b + d * a;
 7        for (var j = 2; j <= n; j++)
 8        {
 9            tmp1 = tmp2;
10            tmp2 = tmp3;
11            tmp3 = c * tmp2 + d * tmp1;
12        }
13
14        return tmp3;
15    }
16}

Analysis of the algorithm

We denote $T(n)$ as the number of additions and multiplications performed during the execution of the program. It is immediate from the code above that $T(n)=3(n-1)$​ (the loop is executed $n-1$ times with 2 multiplications and an addition each time).

$$\boxed{T(n)=O(n)}$$

Thus, this algorithm is significantly better than the previous one. Its linear time is "only" linear, making it suitable for larger values of $n$. Nevertheless, for very large values of $n$, it begins to exhibit inefficiency.

Algorithm 3

The third algorithm involves linear algebra and matrix calculus. For those versed in these matters, it can be intriguing to delve into the steps. However, for those uninterested in the intricate details or less proficient in mathematics, feel free to skip directly to the conclusion.

The recurrence relation can be written $\begin{pmatrix} u_{n-1} \\ u_{n} \end{pmatrix}=\begin{pmatrix} 0 & 1 \\ d & c \end{pmatrix}\begin{pmatrix} u_{n-2} \\ u_{n-1} \end{pmatrix}=M\begin{pmatrix} u_{n-2} \\ u_{n-1} \end{pmatrix}$ for all $n \ge 2$.

Through induction, we easily derive that $\begin{pmatrix} u_{n-1} \\ u_{n} \end{pmatrix}=M^{n-1}\begin{pmatrix} u_{0} \\ u_{1} \end{pmatrix}$ for all $n \ge 2$ so that we are now addressing another problem: the need to compute the $n$-th power of a matrix.

We will commence by coding an algorithm that multiplies two matrices, where one matrix has $r$ rows and $p$ columns, and the other has $p$ rows and $m$ columns. Note that this is surely not the state-of-the-art algorithm, but we will see that it is inconsequential for our case.

 1public class Matrix
 2{
 3    private double[,] _matrix;
 4    private int _rows;
 5    private int _columns;
 6
 7    public Matrix(int rows, int columns)
 8    {
 9        _rows = rows;
10        _columns = columns;
11
12        _matrix = new double[rows, columns];
13        for (int i = 0; i < rows; i++)
14        {
15            for (int j = 0; j < columns; j++)
16            {
17                _matrix[i, j] = 0.0;
18            }
19        }
20    }
21
22    public double[,] Inner => _matrix;
23
24    public int Rows => _rows;
25
26    public int Columns => _columns;
27
28    #region Public Methods
29
30    public Matrix Multiply(Matrix B)
31    {
32        var n = _rows;
33        var p = B.Rows;
34        var m = B.Columns;
35
36        var res = new Matrix(n, m);
37        for (var i = 0; i <= n-1; i++)
38        {
39            for (var j = 0; j <= m-1; j++)
40            {
41                for (var k = 0; k <= p-1; k++)
42                {
43                    res.Inner[i, j] = res.Inner[i, j] + _matrix[i, k] * B.Inner[k, j];
44                }
45            }
46        }
47
48        return res;
49    }
50
51    #endregion
52}

From there, we can formulate an algorithm that computes the $n$-th power of a matrix. To achieve that, we employ the most efficient algorithm derived in the previous article (where we need to calculate the power of a real number), which has a logarithmic time complexity.

 1public Matrix Power(int n)
 2{
 3    if (n == 0)
 4    {
 5        var identity = new Matrix(Rows, Rows);
 6        for (var i = 0; i <= Rows-1; i++)
 7        {
 8            identity.Inner[i, i] = 1.0;
 9        }
10
11        return identity;
12    }
13
14    if (n == 1) return this;
15
16    if (n % 2 == 0)
17    {
18        var square = Multiply(this);
19        return square.Power(n/2);
20    }
21
22    if (n % 2 == 1)
23    {
24        var square = Multiply(this);
25        var res = square.Power((n-1)/2);
26
27        return Multiply(res);
28    }
29
30    return null;
31}

It is now time to analyze these algorithms. For the latter one, we will denote $C(X, n)$ as the number of calls to the Multiply method (X is the matrix under consideration), aiming to derive a formula based on $n$.

From the code, $C(X, n)=0$ if $n=0$ or $n=1$ and $C(X, n) \le 2 + C(X^2, \lfloor\dfrac{n}{2}\rfloor)$ for all $n \ge 2$. We have already encountered this recurrence formula in the last article, and we saw that $C(X, n) \le 2log_{2}n$.

It remains to compute the time complexity of the Multiply method. We will denote $D(X, r, p, m)$ as the number of multiplications and additions. From the code, we derive that $D(X,r,p,m)=2pmr$ (this result is straightforward as there are 3 nested loops and the innermost one involves one multiplication and one addition). As a consequence, for square matrixes ($p$ rows and $p$ columns), we have $D(X, p)=2p^3$.

All things considered, we can now conclude that $C(X, n) \le 2p^3*2log_{2}n=4p^3log_{2}n$ where $p$ is the size of the square matrix X.

Finally, the code for our third algorithm can be built from the previous methods.

 1public class MatrixComputeSequence : IComputeSequence
 2{
 3    public double ComputeSequence(double a, double b, double c, double d, int n)
 4    {
 5        var M = new Matrix(2, 2);
 6        M.Inner[0, 0] = 0.0; M.Inner[0, 1] = 1.0;
 7        M.Inner[1, 0] = d; M.Inner[1, 1] = c;
 8
 9        var P = M.Power(n-1);
10
11        return a * P.Inner[1, 0] + b * P.Inner[1, 1];
12    }
13}

Analysis of the algorithm

Here, we have a 2x2 matrix for which we want to calculate the $(n-1)$-th power. If once again we denote $T(n)$ as the number of additions and multiplications performed during the execution of the program, we can conclude based on what we have just derived that $T(n) \le 4*2^3log_{2}(n-1) +3=32log_{2}n +3$.

$$\boxed{T(n)=O(log_{2}n)}$$

The time complexity is therefore logarithmic, which is a highly desirable property. This algorithm is well-suited for very large values of $n$ and should be prioritized in real-world applications.

How to verify our analyses ?

In this final section, we will attempt to demonstrate that our previous theoretical computations align with reality. To achieve this, we will execute the algorithms with various values of $n$. Note that the first algorithm is disregarded here because it is so inefficient that its execution time is infinite for the values we are considering.

nalgorithm 2 (in ms)algorithm 3 (in ms)
1000000011
1000000005111
100000000048881

It is evident that the third algorithm executes faster than the others. This confirms our earlier analyses.

Final thoughts

In this article, our goal was to provide a comprehensive overview of what time complexity is and how it is influenced by the implementation and design of an algorithm.

If you wish to delve deeper into this topic, acquire the following books, which encompasse all the concepts emphasized in this series and delves into more advanced ones.

The following resource is specifically dedicated to this topic, but it is intended for an advanced audience and requires strong mathematical skills.

[Introduction to the Analysis of Algorithms(https://amzn.to/3vOTAMZ)

Do not hesitate to contact me shoud you require further information.