I have an algorithm that runs in ON^1/2), where n is the size of the problem. For N = 100, the time the algorithm runs is 1 minute. How long does the algorithm take for N=1000? A) Same time B) About 3 minutes C) About 10 minutes D) You haven't given enough information. I can't tell.

Question

Quizplus · Accepted Answer

The algorithm runs in O(N^1/2), so the time is proportional to the square root of N. For N=100, the time is 1 minute. For N=1000, the time is proportional to sqrt(1000)/sqrt(100) = sqrt(10), which is approximately 3.16. Therefore, the time is about 3 minutes.

I Have an Algorithm That Runs in ON1/2), Where N

I Have an Algorithm That Runs in ON^1/2), Where N