Menu
What is the smallest value of n such that an algorithm whose running time is 100n^2 runs faster than an algorithm whose running time is 2^n on the same machine?
The Scope
Although I am interested in the answer, I am more interested in how to find the answer step by step (so that I can repeat the process to compare any two given algorithms if at all possible).
From the MIT Press Algorithms book
499
You want the values of n where 100 × n2 is less than 2 × n. Which is the solution of 100 × n2 - 2 × n < 0, which happens to be 0 < n < 0.02 .
What is the smallest value of n such that an algorithm whose running time is 100 n 2 100n^2 100n2 runs faster than an algorithm whose running time is 2 n 2^n 2n on the same machine? For A to run faster than B, 100 n 2 100n^2 100n2 must be smaller than 2 n 2^n 2n.
Explanation: For inputs of size n, running time of algorithm A is 100n2 and of B is 2n. For A to run faster than B, 100n2 must be smaller than 2n.
Here running time of algorithms are 50*n3 and 3n ,if we compare both as shown in the following table, we find that 10 is the smallest value of n (9.8) for which 50*n3 will run faster than 3n .
You want the values of n where 100 × n2 is less than 2 × n.
Which is the solution of 100 × n2 - 2 × n < 0, which happens to be 0 < n < 0.02.
One thousand words:
EDIT:
The original question talked about 2 × n, not 2n (see comments).
For 2n, head to https://math.stackexchange.com/questions/182156/multiplying-exponents-solving-for-n
Answer is 15
166
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
