4

If I know complexity of an algorithm, can I predict how long it will compute in real life?

A bit more context: I have been trying to solve university assignment which has to find the best possible result in a game from given position. I have written an algorithm and it works, however very slow. The complexity is O(n)=5^n . For 24 elements it computes a few minutes. I'm not sure if it's because my implementation is wrong, or if this algorithm is simply very slow. Is there a way for me to approximate how much time any algorithm should take?

Improve this question

2 Answers 2

Reset to default
4

Worst case you can base on extrapolation. So having time on N=1,2,3,4 elements (the more the better) and O-notation estimation for algorithm complexity you can estimate time for any finite number. Another question this estimation precision goes lower and lower as N increases.

What you can do with it? Search for error estimation algorithms for such approaches. In practice it usually gives good enough result.

Also please don't forget about model adequateness checks. So having results for N=1..10 and O-notation complexity you should check 'how good' your results correlate with your O-model (if you can select numbers for O-notation formula that meets your results). If you cannot get numbers, you need either more numbers to get wider picture or ... OK, you can have wrong complexity estimation :-).

Useful links:

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

You cannot predict running time based on time complexity alone. There are many factors involved: hardware speed, programming language, implementation details, etc. The only thing you can predict using the complexity is expected time increase when the size of the input increases.

For example, personally, I've seen O(N^2) algorithms take longer than O(N^3) ones, especially on small values of N, such as it is in your case. And by, the way, 5^24 is a huge number (5.9e16). I wouldn't be surprised if that took a few hours on a supercomputer, let alone on some mid-range personal pc, which most of us are using.

Improve this answer

4 Comments

While you can't predict it accurately, you can calculate an upper bound for N if you have the complexity and a time limit. It seems the complexity is worst-case O(5^N), which means that further analysis would be required to estimate it.
@bdean20: Well, no. The whole point of O-notation is that you can't compute such an upper bound.
@tmyklebu, read it again. You can compute an upper bound for N. Going on the assumption that O(n) always has a minimum constant factor of 1 (which is a guarantee in physical systems if we assume the problem isn't reduced automatically by compiler optimisation).
@bdean20: You can't assume that. Upper bounds do not, in and of themselves, imply lower bounds. Asymptotic bounds do not imply concrete bounds, though sometimes the same technique can be used to prove an asymptotic bound and a concrete bound.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.