Question

Algorithm complexity question

Answer 1

Algorithm A: N^3/75 - N^2/4 + N + 10

Algorithm B: N/2 + 8

As Algorithm A is made up of a number of polynomial terms, the highest order term, O(N3), cannot be used to determine its theoretical performance. The supplied choice is accurate in stating that Algorithm B's theoretical performance is O(N).

Algorithm B is more effective than Algorithm A based on theoretical performance, as O(N) grows less quickly as N increases than O(N3).

Algorithm A might occasionally perform better than Algorithm B for specific values of N, though. We need to compare the steps for both algorithms in order to determine those values:

N^3/75 - N^2/4 + N + 10 < N/2 + 8

We can resolve this inequality to determine the range of N numbers for which Algorithm A performs better than Algorithm B. To determine approximate values of N where this inequality holds because it is difficult to solve analytically, we can utilize numerical techniques or graphing tools.

Algorithm A would perform better than Algorithm B for what values of N?

where N ≈ 1 and N ≈ 2

What values of N do Algorithm B and Algorithm A perform better for?

where N < 1 or N > 2

The real values may change significantly from these approximations, so it's important to keep that in mind. A root-finding algorithm or graphing the functions are two numerical techniques I'd suggest as a professor to better comprehend the precise values at which the inequality holds true.

Despite the fact that Algorithm B theoretically performs better overall, Algorithm A is more effective for some values of N (about 1 and 2). Algorithm B performs better for N values of less than 1 or more than 2.

Answer 2

• A: O(N³)
• B: O(N)
• Algorithm B is more efficient than Algorithm A
• N ≥ 5 and ≤ 15
• N ≤ 4 or ≥ 16

Step-by-step explanation:

You want to compare the theoretical performance and actual performance of Algorithm A, which requires N³/75 -N²/4 +N +10 steps, and Algorithm B, which requires N/2 +8 steps.

Theoretical performance

The theoretical performance of an algorithm is generally described by the shape of the performance curve when N gets large. Constant factors are generally ignored. When the number of steps is described by a polynomial, the performance is described by the highest-degree term.

• Algorithm A: O(N³)
• Algorithm B: O(N)

The number of steps increases faster for large N using algorithm A, so we conclude that ...

Algorithm B is more efficient than Algorithm A

Practical performance

When we plot the number of algorithm steps versus N on a graph, as in the attachment, we find that Algorithm B takes more steps for specific values of N. For those values, Algorithm A outperforms Algorithm B.

• A outperforms B where N ≥ 5 and N ≤ 15
• B outperforms A where N ≤ 4 or N ≥ 16

__

Additional comment

We presume that the problem size is measured using integer values of N. That is why we have used integer values in the answers to the practical performance questions. The graph shows the boundary values to 3 decimal places if needed. (As, for example, if N is measured in thousands.)

Algorithm performance can follow a number of different curves. The usual ones are polynomial, exponential, logarithmic, or some product of these, as O(N·log(N)), for example.