Matti's CS Notebook

• Introduction to algorithms, Cormen et al. (2022)
• 1: The role of algorithms in computing
• 1.2 Algorithms as technology

Problems 1-3

1 At the end of the day, all software applications are “algorithmic” or “require algorithmic content” because all information processing done at computer is ran by more or less well defined algorithms, i.e. by a routine that terminates with a correct output.

2 Given an algorithm $A$ that executes in $8n^2$ steps and an algorithm $B$ that executes in $64 n \lg n$ steps, the value on $n$ for which algorithm $B$ executes faster than $A$ can be modeled by the inequality

Before trying to solve the inequality, it’s good to notice that the inequality can be factored by dividing both sides by $8n$, so the inequality becomes

One way to figure out a proper value for $n$, for which the inequality $(1)$ no longer holds, that is, when $B$ becomes faster than $A$, is to solve the problem numerically and write a computer program that outputs the value of $n$, when $(1)$ is no longer true. Such a program is one that executes the following function,

void f() {
    for (double n = 2.0; n > 0.0; n += 1.0) {
        if (n >= 8.0 * std::log2(n)) {
            std::println("n = {}", n);
            n = -1.0;
        }
    }
}

Since input of size $n = 1$ is already sorted, no sorting is needed, so solving the inequality $(1)$ starts assuming with $n = 2$ — See line 2 of the above code. Running the function $f$ as part of a program shows that when $n = 44$, the algorithm $B$ outperforms algorithm $A$, because then

that is the inequality no longer holds. If $n = 43$, the inequality $(1)$ becomes

which is the last value of $n$, when algorithm $A$ performs better than $B$.

3 Similarly as in the previous solution, the running time relation of the two algorithms $A$ and $B$ can be modeled by the inequality

where $n$ is the input size. The inequality can be solved numerically by modifying the code of 2, by changing the line 3 from

if (n >= 8.0 * std::log2(n)) {

to

if (std::pow(2,n) >= 100.0 * std::pow(n,2)) {

which leads to function

void f() {
    for (double n = 2.0; n > 0.0; n += 1.0)) {
        if (std::pow(2,n) >= 100.0 * std::pow(n,2) {
            std::println("n = {}", n);
            n = -1.0;
        }
    }
}

Running a program that calls f shows that when $n = 15$ in $(2)$, the inequality no longer holds. Substituting this value of $n$ to the inequality shows that,

which is false, but when $n = 14$ in $(2)$

the inequality $(2)$ is true, so $n = 14$ is the smallest for which the a algorithm $A$ executes faster than $B$. When $n > 15$, algorithm $B$ performs faster.