About Analysis of Algorithms

Question

I have a question on two questions regarding the content of algorithmic analysis.

---

Issues

1. In computer science, an algorithm is a finite sequence of executable actions that seek to obtain a solution to a particular type of problem. Analysis of the items below.

   I. To define the best (fastest) between two algorithms it is necessary to implement both and perform tests.

   II. The running time of an algorithm depends on, exclusively, of the transactions contained therein.

   III. By counting operations processed by two algorithms it is possible to determine which is the most efficient.

   IV. The running time of an algorithm may depend on the input values of the algorithm.

In my analysis, I understand that the running time of an algorithm does not depend on, exclusively, of the operations contained in it. In this case, I believe that item II is incorrect. Maybe I’m wrong, but I believe the other three items are correct. In the feedback, only two items are correct and I can’t get the answer.

2. Given three algorithms. A = 50n+10 operations; B = n ² +15 operations; C = 1000 log 2 n+200 operations. Judge the following items.

   I - Algorithm A is more efficient for inputs larger than 80.

   II - Algorithm A is the most suitable for input size less than 150.

   III - Algorithm B is the most suitable for input size greater than 80.

   IV. - Algorithm B is specified for input size less than 50.

   V. - Algorithm C is best for input size between 50 and 150.

   VI. - Algorithm C has the minor growth rate.

In my analysis of question two, item VI is correct and the item, but the other items end up confused, because, I can not identify whether one is better or worse than the other.

---

These are my doubts, if someone can help me can be with material also supporting, I am studying for the sake of knowledge even, and I think it very important for an analyst in training understand about the complexity process of algorithms.

Answer 1

I. To define the best (fastest) between two algorithms it is necessary to implement both and perform tests.

Whereas this is a question about analyzing algorithms, if you have them just scribbled on paper in pseudocode, you can determine their complexity. If one of them is O(n), while the other is O(n²), you don’t need to implement them and run them on a real machine to know which one is the fastest. So this is fake.

II. The running time of an algorithm depends on, exclusively, of the transactions] contained therein.

IV. The running time of an algorithm may depend on the input values of the algorithm.

Statement IV already shows why II is false. Obviously the input values directly influence the running time of an algorithm. In fact, usually the execution time is given as a function of the input values or size. Therefore, II is false and IV is true.

III. By counting operations processed by two algorithms it is possible to determine which is the most efficient.

If one gives O(n) and the other O(n²), becomes clear which is the most efficient. Therefore, this is generally true. A more refined analysis such as 50n + 10 or 48n + 30 operations also serves to answer this. Hence hence this is true. And it is exactly on this that the second question says.

At which intervals Algorithm A is more efficient than B?

To know this, let’s see the point where both meet. That is, where 50n + 10 = n² + 15:

50n + 10 = n² + 15
0 = n + 50n + 15 10
n' 50n + 5 = 0
n = (50 sqrt(50? 4 1 5)) / (2 1)
n = (50 sqrt(2500 20)) / 2
n = (50 sqrt(2480)) / 2
n = (50 49.8) / 2
n' = (50 49.8) / 2
n' = 0.2 / 2
n' = 0.1
n" = (50 + 49.8) / 2
n" = 99.8 / 2
n" = 49.9

What does this mean? How the calculated equation was y = n pra 50n + 5, We have that is B time minus A time. So if it’s negative, B is faster. If it’s positive, A is faster. If this goes to zero, you both have the same performance. The points where the two perform the same (the roots of the equation) occur with inputs of size 0.1 and 49.9.

The concavity of the resulting parable is turned upwards, so in most cases (those beyond the roots), B takes longer. In the other cases (among the roots), A takes longer. Therefore, B is faster for inputs of size 1 to 49. While the A is faster for inputs of size 0 or greater than or equal to 50. Proof of this is that:

A: 50 0 + 10 = 10 (faster)
B: 0² + 15 = 15

A: 50 1 + 10 = 60
B: 1² + 15 = 16 (faster)

A: 50 49 + 10 = 2460
B: 49² + 15 = 2416 (faster)

A: 50 50 + 10 = 2510 (faster)
B: 50² + 15 = 2515

Now, let’s do the same for A compared to C:

50 n + 10 = 1000 log₂(n) + 200

Unfortunately, finding the root of this equation is somewhat complicated. The same is true when comparing B with C. The question 2 problem requires that the times of A, B and C are all compared, and although you can use equations to find an answer, such as when comparing A with B, in many cases finding them can be difficult and/or laborious.

However, we can use a program and set up a table of values to help us:

function log2(x) {
    return x == 0 ? 0 : Math.log(x) / Math.log(2);
}

for (var n = 0; n <= 600; n++) {
    var a = 50 * n + 10;
    var b = n * n + 15;
    var c = 1000 * log2(n) + 200;

    // Para exibir o c com duas casas decimais se não for inteiro.
    var cx = Math.round(c * 100) + "";
    cx = c % 1 === 0
        ? c
        : cx.substring(0, cx.length - 2) + "," + cx.substring(cx.length - 2);

    var melhor = ""
    if (a <= b && a <= c) melhor += "A";
    if (b <= a && b <= c) melhor += "B";
    if (c <= a && c <= b) melhor += "C";

    var tr = $("<tr></tr>");
    $("<td>" + n + "</td>").appendTo(tr);
    $("<td>" + a + "</td>").appendTo(tr);
    $("<td>" + b + "</td>").appendTo(tr);
    $("<td>" + cx + "</td>").appendTo(tr);
    $("<td>" + melhor + "</td>").appendTo(tr);
    $("#t").append(tr);
}

td, th {
    border-color: black;
    border-width: 1px;
    border-style: solid;
}

table {
    border-spacing: 0;
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<table id="t">
    <tr>
        <th>N</th>
        <th>A</th>
        <th>B</th>
        <th>C</th>
        <th>Melhor</th>
    </tr>
</table>

In this program, there are some points about the logarithm function. This function produces zero when the input is 1 and produces negative values for inputs in the range [0, 1), going to when the input is 0. To solve this, let’s consider that the output is zero when the input is zero, since negative runtime does not exist.

So, looking at the table, we have to:

• For N = 0, A is the best.
• For 1 N 49, B is the best.
• For 50 N 147, the A is the best.
• For N 148, C is the best.

Soon:

I.- Algorithm A is [the] most efficient for inputs larger than 80.

False. This is only valid for cases where the input is between 50 and 147. From there, the C is the most efficient.

II.- Algorithm A is the most suitable for input size less than 150.

False. For inputs up to size 49, the B is the best. For an input of size 148 or 149, the C is the best.

III.- Algorithm B is the most suitable for input size larger than 80.

Fake. Only the best when the input is smaller than 50.

IV. Algorithm B is indicated for input size less than 50.

True since you disregard the case N = 0 (which in various types of algorithms, is something that does not exist).

V. Algorithm C is [the] best for input size between 50 and 150.

Fake. The A is the best when the entrance is between 50 and 147.

VI. Algorithm C has the lowest growth rate.

True. It is for this reason that from a certain point (N 148), it is always better than other algorithms. By growth rate, you can understand as derived:

• To: d(50x + 10) = 50.
• B: d(x² + 15) = 2x.
• C: d(1000 log₂(x) + 200) = 1000 1 / (x ln(2)) = 1442.7 x¹.

Note the degree of each of the expressions. The degree of the derivative of A is 0. The degree of the derivative of B is 1. The degree of the derivative of C is 1. The lower the derivative degree, the lower the rate of variation.

However, you don’t even need to look at the derivative to see that the growth rate of C is lower. Just know that a quadratic function (B) grows faster than a linear function (A), which in turn grows faster than a logarithmic function (C). And therefore:

• Quadratic = O(n²).
• Linear = O(n).
• Logarithmic = O(log n).

And with that, you don’t even have to look at the rest to see which one grows at a higher or lower rate. You would only have to do this if you were to compare two functions of the same class (two different quadratics, for example).