Consider an algorithm A with running time n√n. Assume that A can solve instances of size n on a machine that takes 10−12 seconds per operation. What size instances (in terms of n) can A solve in the same time on a machine that takes 10−15 seconds per operation?
Question
Consider an algorithm A with running time n√n. Assume that A can solve instances of size n on a machine that takes 10−12 seconds per operation. What size instances (in terms of n) can A solve in the same time on a machine that takes 10−15 seconds per operation?
Solution
The running time of the algorithm A is proportional to n√n. This means that if we increase the speed of the machine by a factor of 1000 (from 10^-12 seconds per operation to 10^-15 seconds per operation), we can also increase the size of the instances that the algorithm can solve in the same time by the cube root of 1000, because n√n = n^(3/2), and the cube root of 1000 is 10.
So, if the algorithm can solve instances of size n on the slower machine, it can solve instances of size 10n on the faster machine.
Similar Questions
Given that the efficiency of an algorithm is 5n2 , if a step in this algorithmtakes 1 nanosecond (10–9 seconds), how long does it take the algorithm toprocess an input of size 1000?
An algorithm has liner time complexity and can process an input of size n in a certain amount of time. If the algorithm runs on a computer that has a processor that is 5 times as fast, how large of an input can be processed in the same amount of time? A. n + 5 B. 5n C. n / 5 D. n^5 E. 5^n
An algorithm iterates 10 times for an input of size n. What is the best-case time complexity?
Can you think of any factor that might affect the actualrunning time of an algorithm?Algorithms and Complexity (Sem 1, 2024) Comp. Models & Asym. Notation © University of Melbourne 9 / 1
or analyzing an algorithm which is better computing time?Question 2Answera.О(nlogn)b.Оc.О(100 log n)d.О(n!)
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.