This question here: Algorithmic intuition for logarithmic complexity where the question, and almost all the answers are using BigOh when they really mean Theta and as written, the answers are answering the wrong question (or if you look at it differently, they are incomplete) as they are only explaining Theta(log n).

I tried to let the questioner (and answerers) know about this by leaving a comment on the question (though quite terse) which seems to have been ignored mostly (except for one upvote).

The question is, would it be ok to go and edit the question and answers and if not, how to go about ensuring correctness (eg: leave more comments...)? Some people feel that this is just pedantic nitpicking (from my past experience on SO), but given that this is a computer science site(and not a programming site, where even basic theory seems to be a second class citizen), we should strive for correctness and avoid making basic mistakes like these if we can.

Also, what about such situations in the future? (i.e. do we open up a question for each such situation or have the answers here serve as guidance?)

[Update: OP has edited the question to correct the error]

  • $\begingroup$ Or am I missing something and everything is fine? $\endgroup$ – Aryabhata Mar 22 '12 at 21:16
  • 2
    $\begingroup$ Good question; I have no idea how to handle this. I do think that your comment on that question could have been a bit more elaborate: I'm not sure if the questioner gets what you're asking of him (he evidently doesn't understand landau notation very well). $\endgroup$ – Alex ten Brink Mar 22 '12 at 21:30
  • $\begingroup$ @AlextenBrink: Yeah, I agree it was too terse. I added a more elaborate comment which includes a link to this meta question. $\endgroup$ – Aryabhata Mar 22 '12 at 21:46

I think editing in $\Theta$ instead of O is appropriate as it is clear from context what is intended. Would you do the honors?

In the future, I think the same procedure can be used. Maybe we should have a FAQ-style question on the main site ("Why do people use $\Theta$?") to link to in such cases; this one might do, but the answer do not elaborate why $\mathcal{O}$ is often (usually?) meant to be $\Theta$.

  • 1
    $\begingroup$ Seems like people don't visit meta too often. The lack of downvotes to your answer is reason enough for me to go an edit them, and I am going to do that now. EDIT: Done, I think. $\endgroup$ – Aryabhata Mar 23 '12 at 19:49
  • $\begingroup$ Would you care to update your answer with some viewpoint regarding the general question? $\endgroup$ – Aryabhata Mar 26 '12 at 3:39

I'm the asker of that question, and I didn't know this. I think it's acceptable for you to edit this to use theta provided that you leave a comment explaining this. I am here to learn after all.

@Alex, no I don't understand landau notation at all.


You must log in to answer this question.

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