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,∞)
