Complexity

In your future job, it is possible that someone asks for your opinion on a new calculation software. Most people will focus on the user-friendliness. Some of them will focus on the proposed features. Both are important. However, few will ask the question, is this software a viable option for the type of problem that we have to solve today and tomorrow?

As mentioned before in the profiling section, the asymptotic complexity is defined as the cost of a solution as function of the problem size neglecting the smaller order terms. Later on, “complexity” implies asymptotic complexity. An answer that you obtain for a problem of size 1_000 in 1 s may take one hour, one month, or the age of the universe for a problem or size 1_000_000 depending on the algorithm complexity. The same question can be studied concerning other resources such as the memory usage.

• Define a base costly operation whose cost is independent of the problem size. In the most simple case, the multiplication / division between two scalars is the costly operation.

• Count for a problem of size \(N\) the number of required costly operations. Keep only the highest order term.

  The number of operations is either deterministic or probabilistic. In the later case, one may talk about the minimum, maximum, mean … complexity.

Exercise (easy)

1. Can a matrix multiplication of size \(N \times N\) be used as the costly operation?

2. If you develop a software where many 3d vector rotations using \(3 \times 3\) matrices and length 3 vectors are required, can a single vector rotation can be defined as the costly operation?

3. What is the time complexity of the multiplication between two \(N \times N\) matrices if the multiplication between two scalars is the costly operation?

4. You decide to store the distance between cities in a double entry table (first column an first row are the city names). What is the memory complexity?

Correction

1. No, must be fixed size.

2. Yes, is fixed size.

3. \(N^2\) coefficients, \(N\) multiplications per coefficient, which gives \(N^3\).

   \[\begin{split}\begin{align*} C &= A \, B \\ C_{ij} &= \sum\limits_{k=1}^{N} A_{ik} \, B_{kj} \end{align*}\end{split}\]

4. \(N^2\) distances. (Even if only the upper triangular part of the table is allocated and used.)

Exercise (easy)

1. Give two methods to verify that a list of ints does not contain any duplicates?

2. What are the time complexities if the equality comparison between two numbers is the costly operation?

Correction

1. Comparing each item to every following item, or inserting every list element into a set.

2. \(N-1 + N-2 + \cdots + 1\) which gives \(N^2\) (the factor one half does not matter), or \(N\) times constant time which gives \(N\).

Exercise (intermediate)

What is the time complexity of the solution process of an upper triangular system (without 0 on the diagonal)?

Hint

Fill up the table:

row	\(*\)	/	total
N
…

Correction

\(N^2\) multiplications or divisions. From bottom to top:

\[\begin{split}\begin{align*} A x &= b \\ x_{i} &= \cfrac{b_i - \sum\limits_{k=i+1}^{N} A_{ik} x_k}{A_{ii} } \end{align*}\end{split}\]

row	\(*\)	/	total
N	0	1	1
N-1	1	1	2
N-2	2	1	3
N-i	i	1	i+1
1	N-1	1	N
			N(N+1)/2

Exercise (intermediate)

The algorithm described in the student - project assignment discussion gives a stable solution. This solution might not be unique and other criteria could be used to pick an “optimal” solution. For example, the solution maximizes the preference score of the least well served student could be interesting (fairness). To break up ties, other criteria might be used such as the sum of the preference score of all the choosers (maximum utility).

A new algorithm is proposed: for all possible iteration orders between choosers through all_choices, run assign to obtain all the stable assignments, then select the fairest one.

1. What is the time complexity for \(N\) choosers and \(N\) choices?

2. If it takes 2ms for \(N=10\), how long will it take for \(N=26\)?

Correction

1. \(N!\) possible iteration chooser orders. One assign implies \(N^2\) checks of a project availability at worse (defined here as a constant time costly operation) if every student rank all the projects in the same order for the assignment of a choice. Thus, this first step requires \(N^2 N!\) operations.

   \(N!\) potential assignments exist. The stable assignment solutions (assignments and scores) obtained from assign are a subset of those potential assignments. The fairness evaluation implies to get the minimum score between choosers and then maximize between all the obtained stable solutions. A single minimum look-up is \(N\). As a result, this second step is order of magnitudes less time consuming than the first step.

   The overall complexity is \(N^2 N!\).

2. \(\cfrac{26^2 26!}{10^2 10!} \cfrac{2}{1000 \cdot 3600 \cdot 24 \cdot 365 \cdot 14E9}\approx 3\) times the universe age.