Question

There are two algorithms:

–Algorithm A requires 5*n2 time units to solve a problem of size n.

–Algorithm B requires 7*n time units to solve a problem of size n.

Draw a chart (graph) to show the performance of the programs.

Answer 1

Algorithm A requires: 5*n^(2) and Algorithm B requires: 7*n time units to solve a problem of size n

Below are the graph which shows the performances of Algorithm A and Algorithm B for different case:

Case1: very large values of n: ~ 10^(9)

As we can observe that performance of Algorithm is extremly worse than that of Algorithm B, this shows that Algo B outperforms Algo A for Larger values of n

Case2: Medium value of n: ~ 10^(4)

In this case also Algo A's performance is extremely worse as compared to Algo B

Case3: Small value of n: ~100

In this case also performance of Algo B is much better than Algo A.

Case4: Small value of n: ~10

In this case also performance of Algo B is still fairly better than Algo A

Case5: very small value of n: ~ 2

We can observe from this graph that for some value of n, between 0 and n, performance of Algo A is better than Algo B.

Equating these two equations: 5*n^(2) = 7*(n) => n = 0, 1.4

Therefore in range 0 to 1.4 Algo A is better than Algo B and since n is integer therefore, it can have only value of 1 in that range, therefore, for n=1, Algorithm A performs better than Algorithm B

Conclusion:

for all integer values of n except 1, Algorithm B is better than Algorithm A