An algorithm takes 1 second to execute for an input size of 10. What will the largest size of
input be that can be executed in 25 seconds if the running time is quadratic (N2)? Can i also have links to literature that can give me clear examples or explanations, i can follow through.

Recommended Answers

All 3 Replies

If the running time is equal to n^2 u for some unit u, then you can easily solve for u in 10^2 u = 1 second and then insert the solution in 25^2 u.

If the running time is merely in Theta(n^2) (which is usually what we mean when we say that the running time of something is quadratic), then the question is not answerable.

You have two equations:

C * 10^2 = 1
C * N^2  = 25

You can solve that for your two unknowns C and N. If you cannot figure out how to solve that, go back to high-school.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.