Answer the question to continue ...

Complexity of algorithms

To achieve this, we use binary search. For this, first we choose an item in the middle of the remaining list, check if the number is 24 or if 24 is smaller or greater than this number and then take either the left (when 24 is smaller) or right subset (when 24 is bigger). We continue until we have no more items left to check.

For 12 items, this already is quite a difference in the number of checks needed. And if we look at lists with 10.000 or even 100.000 elements, the difference gets even bigger. Searching a sorted list with 10.000 entries requires 14 checks, a list with 100.000 entries 17.

We see, when comparing algorithms we are normally not interested in specific numbers but more in the overall runtime complexity they have.

The runtime complexity of an algorithm describes how the execution time changes with the size of the input data. To make runtime complexity comparable across hardware, it is not the exact runtime but rather the number of operations that is measured.

Also, runtime complexity is not about the precise number of operations needed, but the overall trend describing how the number of operations grows with input size. That's why we are mostly looking into the worst-case complexity (e.g. search for an item not in the list). While search in an unsorted list scales linearly with the input size \(n\) (which is described by the function \(f(n)=n\)), the search in a sorted list only scales logarithmically with the input size (which is described by the function \(f(n)=\text{log}(n)\)):

Algorithms' runtime complexity is compared using the most dominant term in the term describing the number of operations. An algorithm that needs \(n+5\) operations would be considered to be part of \(\mathcal{O}(n)\), whereas an algorithm that requires \(2^n + n^3 \) operations would be considered in \(\mathcal{O}(2^n)\). For the symbol being used, this is also refered to as the big-O notation.

The plot below shows how different runtime complexities scale with increasing input size. And we see, why it actually makes sense to investigate better algorithm than only relying on better or faster hardware.

Typically encountered runtime complexities are:

• Constant time such as finding the median value in a sorted list
• Logarithmic time such as checking if a value is contained in a sorted list
• Linear time such as checking if a value is contained in a unsorted list
• Quadratic time such as creating a sorted list by repeatedly searching for the minimal value in the provided list. (This is called selection sort.)
• Expontential time such as solving the maximum cut problem.
• Factorial time such as brute forcing all potential round trips one can make through \(n\) selected cities from the vacation country. (This is called the travelling salesman problem).

For some problems, algorithms are so complex that they require exponential or even factorial time to run, making it unfeasable to solve. In quantum computing we look for algorithms that can solve such problems much faster.

Take it further: Running algorithms on a spaghetti computer...

It should be noted that computational complexity of a given problem is not uniquely determined. It may depend on the algorithm and/or the computational resource.
Let us consider the sorting problem where we are given \(n\) positive numbers that we need to sort. This can be achieved with a conventional computer in quadratic time \(\mathcal{O}(n^2)\) (some algorithms do it in \(\mathcal{O}(n ~\text{log}(n))\) though).

This may be reduced to linear time \(\mathcal{O}(n)\) if we use spaghettis as the computational resource. Therefore, we encode the \(n\) positive numbers with the length of spaghettis by cutting each spaghetto to an appropriate size, which takes \(n\) steps. Then we grab all strands of spaghetti loosely and press them against the desk so that they stand upright, which requires 2 steps. Then you pick up the longest one and put it in the far right. Then pick up the next longest one and place it next to the first one and so on until you exhaust all strands, which requires \(n\) steps. Now spaghetti are arranged in descending order with \(2n + 2\) steps, namely the computational complexity is reduced to linear time \(\mathcal{O}(n)\) by this “spaghetti computer”.

One might argue that each step of a spaghetti computer takes much longer time than that of a digital computer. Suppose each step of a spaghetti computer takes \(C\) times more time than that of a digital computer. Then there is a crossover of the two algorithm at \(n^2 ∼ Cn \), namely at \(n ∼ C\). Supremacy of a spaghetti computer is guaranteed if \(n\) is much larger than \(C\).

Is this always true? In fact, we must be careful when we consider physics. Suppose the length of each spaghtto is \(L\). Can \(n\) be arbitrarily large? It is not! A spaghetti computer is impossible if \(n\) is so large that \(\frac{L}{n}\) is as small as the atomic size. Then you cannot cut the spaghetto into a given length and the algorithm is no longer applicable.

What we have learned here is that applicability of an algorithm depends on the physical resource of computation. Similiarly to a "spaghetti computer", a quantum computer has its own physical resource of compution, which allows us to make use of superposition and entanglement and opens for completely new algorithms.