Is it "frowned upon" in whatever capacity to, when a user asks a question about asymptotic complexity analysis of some algorithm, suggest implementation-dependent improvements, should the user potentially wish to implement the algorithm?

E.g. I responded to Is there a way to find path length to a node from root in a binary tree? with "If whatever language you plan to use to implement this should have it as a feature, you should take advantage of tail-call optimization. It would reduce your space complexity to O(1) (while still making a simple solution with recursion)" and had my suggestion addressed by a mod as irrelevant, hence my asking here.

  • $\begingroup$ As a user, I thought your comment was unlikely to help the OP but bore potential to confuse. Hence my comment. (Also what Luke writes.) $\endgroup$ – Raphael Mar 7 '15 at 19:20

I think in this case there's a few of intertwined things:

  1. I suspect that Raphael was commenting with his user hat on, rather than his mod hat - that is, his comment should be viewed as his interpretation and contribution, rather than a ruling in his capacity as a moderator (not that I'm suggesting you necessarily thought this, but it's a point worth making in this situation).
  2. The question itself, to me at least, seems like a question encountered in a basic theory and/or algorithms course (not that it necessarily was, just that the content and level is equivalent), and thus suggestions for implementation details are in some sense "outside the scope of the question". So from a pedagogical perspective, which in some sense is the perspective from which questions are answered on a Stackexchange site, it is superfluous and perhaps confusing to add tangential comments. The ideal would be that the questioner, if they were interested in implementation, would then ask a second question. The problem of course is whether a comment or answer (or part thereof) is tangential is sometimes a matter of opinion, but to balance this, there's a voting, editing and eventually a moderation system (which is reserved for abuses of the system).
  3. There's an ongoing effort to provide as clean a demarcation between CS and StackOverflow, for a number of reasons, but basically to assist in curation and helping people to find the information in the future. SO tends to migrate the theoretical, non-implementation related questions to CS, and CS tends to migrate the implementation specific questions to SO. This system is not perfect, bits of both end up in both places, and the precise line is hard to identify; there's broad implementation issues that are quite at home on CS, rather than SO, and so on. For example a question about the theory of tail-recursion and optimisation would be perfectly acceptable, a question about whether and how Haskell does it would be outside the scope of CS.

So for your comment in particular, I think #2 is the central issue, though #3 probably plays into it, but again, in this case, I wouldn't take Raphael's status as a mod as important, so it's not an issue of policy.

  • 2
    $\begingroup$ ad 1) Yes, definitely. ad 2) Implementation questions as follow-up should probably go to Stack Overflow, anyway. Depends on the level of the issue, i.e. whether it's language agnostic. $\endgroup$ – Raphael Mar 7 '15 at 19:19

In cases where it looks like the asker might be interested in implementing the algorithm, brief suggestions about implementation might be appropriate. That would apply particularly in cases where somebody is asking for an algorithm to solving some very practical-looking, real-world kind of problem.

The comment you're asking about is certainly brief but the question doesn't seem appropriate for it. First, it's a theoretical-type question. Second, and this is the big give-away, the question isn't asking for an algorithm but about a complexity analysis (strictly speaking, runtime analysis) of a specific algorithm. This isn't a question about optimizing constant factors by using tail-recursion: it's a question from the "n^100 is polynomial so it's fine; 1.001^n is exponential so it's bad" world.

Long story short: brief suggestions for implementers can be OK but I don't think that particular comment was relevant to that particular question.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .