Question

The running time of Algorithm A is (1/4) n2+ 1300, and the running time of another Algorithm B for solving the same problem is 112n − 8. Assuming all other factors equal, at what input size(s) would we prefer one algorithm to the other?

Answer 1

Answer:

Answer is explained below

Explanation:

The running time is measured in terms of complexity classes generally expressed in an upper bound notation called the big-Oh ( "O" ) notation. We need to find the upper bound to the running time of both the algorithms and then we may compare the worst case complexities, it is also important to note that the complexity analysis holds true (and valid) for large input sizes, so, for inputs with smaller sizes, an algorithm with higher complexity class may outperform the one with lower complexity class i.e, efficiency of an algorithm may vary in cases where input sizes are smaller & more efficient algorithm might be outperformed by the lesser efficient algorithms in those cases.

That's the reason why we consider inputs of larger sizes when comparing the complexity classes of the respective algorithms under consideration.

Now coming to our question for algorithm A, we have,

let F(n) = 1/4x² + 1300

So, we can tell the upper bound to the function O(F(x)) = g(x) = x2

Also for algorithm B, we have,

let F(x) = 112x - 8

So, we can tell the upper bound to the function O(F(x)) = g(x) = x

Clearly, algorithmic complexity of algorithm A > algorithmic complexity of algorithm B

Hence we can say that for sufficiently large inputs , algorithm B will be a better choice.

Now to find the exact location of the graph in which algorithmic complexity for algorithm B becomes lesser than

algorithm A.

We need to find the intersection point of the given two equations by solving them:

We have the 2 equations as follows:

y = F(x) = 1/4x² + 1300 __(1)

y = F(X) = 112x - 8 __(2)

Let's put the value of from (2) in (1)

=> 112x - 8 = 1/4x² + 1300

=> 112x - 0.25x² = 1308

=> 0.25x² - 112x + 1308 = 0

Solving, we have

=> x = (112 ± 106) / 0.5

=> x = 436, 12

We can obtain the value for y by putting x in any of the equation:

At x=12 , y= 1336

At x = 436 , y = 48824

So we have two intersections at point (12,1336) & (436, 48824)

So before first intersection, the

Function F(x) = 112x - 8 takes lower value before x=12

& F(x) = 1/4x² + 1300 takes lower value between (12, 436)

& F(x) = 112x - 8 again takes lower value after (436,∞)

Hence,

We should choose Algorithm B for input sizes lesser than 12

& Algorithm A for input sizes between (12,436)

& Algorithm B for input sizes greater than (436,∞)