Question

Algorithm A performs \(10 n^{2}\) basic operations, and algorithm B performs \(300 \ln n\) basic operations. For what value of \(n\) does algorithm \(\mathrm{B}\) start to show its better performance?

Short answer

Algorithm B starts to show its better performance for \(n\) values greater than about 7.395

Step-by-step solution

Set up the equation

We start by setting up the equality between the two time complexity equations to find the 'crossover point' where Algorithm B becomes faster than Algorithm A. The equation is therefore: \(10n^2 = 300\ln{n}\)

Simplify the equation

Next, we simplify the equation by dividing all terms by 10 to reduce complexity: \(n^2 = 30\ln{n}\)

Solving the equation

This is a transcendental equation and it's not simple to solve analytically. We can use numerical methods or graphical methods to solve it. A widely accepted method is using a computational tool (like a graphing calculator or a software like MATLAB or Python) to solve this equation.

Approximate the solution

Using a numerical approximator, you'll find that the equation \(n^2 = 30\ln{n}\) becomes true for \(n \approx 7.395\). That is, when \(n\) is greater than this number, the value of \(30\ln{n}\) will exceed \(n^2\), meaning algorithm B performs better.