3
$\begingroup$

I am new to programming and want to learn how to compare algorithms having the same complexity and pick the best one. Certain problems can be sloved using several algorithms which have the same complexity. How do i compare such algorithms

$\endgroup$
3
$\begingroup$

By "having the same complexity" I assume you mean having the same time complexity.

If you have done fine analysis of time complexity of these algorithms then there may be hidden constants or factors of lower degree polynomials which are ignored when you compare using big-O notation but have effect in practice. For example, if one algorithm always takes $n^2 + 100n + 10000$ steps and the second one takes $0.3n^2$ then the second one would be a better choice, though both run in $O(n^2)$.

You could also consider their space complexity and choose one which consumes less memory if the memory consumption matters and more important than the time complexity.

If you aim to implement these algorithms yourself and use it in your commercial application (or something like that) then you could think about how easy they are implemented and how easy these algorithms scale.

$\endgroup$
  • 2
    $\begingroup$ @rus9384 it seems that you understand the problem with tag wideness. I think that this answer is very good (+1), aims at the most probable dilemma, was accepted and covers several aspects, including the problem with comparing complexity in Landau notation for practical-size inputs. If you have some insight about the circuits complexity and parallelization complexity, please add your answer, it would be great. I am not convinced that someone would need it though. For parallel env you can set your $k$ as the number of cores, run tests etc. (The last one is covered here). $\endgroup$ – Evil Sep 30 '17 at 16:18
  • $\begingroup$ One good way to deal with ambiguous questions to post a comment under the question requesting that the question be edited with clarification of whatever points are ambiguous. $\endgroup$ – D.W. Sep 30 '17 at 23:37
1
$\begingroup$

If you develop software, it doesn't matter how fast an algorithm is, what matters is that it meets your requirements. Once you have an algorithm that works, and meets the requirements, the cost of making a second algorithm work, and comparing it with the first algorithm, can be very high. And you have only a 50% chance that the second algorithm is better, and a possibly much lower chance that it is better in a meaningful way.

$\endgroup$
  • 1
    $\begingroup$ "...only a 50% chance...". - How big is the chance too see phoenix out of window? - Um, 50%? $\endgroup$ – rus9384 Sep 30 '17 at 15:49
  • 1
    $\begingroup$ It is an educated guess, so it should be more than 50% chance, dimnishing with consecutive tryouts. Also it seems to solve only one angle, the commercial one (maintainability, development cost) where the time is valuable. But it solely depends on the task, for example if the objectives are "optimise the running time for given size of the input", then testing various solutions is unevitable, but not wrong. Also the developer with 50% chance of initial optimizing and mayhap no testing whatsoever is not really valuable asset... $\endgroup$ – Evil Sep 30 '17 at 16:07
  • $\begingroup$ @Evil, in ideal universe 50% guess would be the most likely due to normal distribution. Yet, there are many examples from my life that distribution in our world is not normal, whatever you take. $\endgroup$ – rus9384 Sep 30 '17 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.