This seems very field-specific. In some fields -- e.g. philosophy -- "criticizing the work of others" is more than business as usual: it's a substantial part of what all papers in the subject do. (Philosophy is probably the extreme case: though I am far from an expert in this area, I do have some familiarity with it, and my understanding is that a truly correct and unassailable philosophical argument would in most cases serve to show that the problem was not really philosophical at all! This is a field in which the rank and file philosophers of today criticize the golden gods of the past two thousand years as well as each other...and everyone seems pretty happy about it.) In certain other fields there is the sense -- and this can only be meant sociologically without opening up some truly deep cans of worms -- that "right" and "wrong" work is not a matter of individual opinion or belief: it is something that the community as whole must come to an agreement on. For instance, two scholars can happily present rival theories on the meaning of Hamlet or even on its authorship. Two scholars who report inconsistent physical experiments cannot coexist so happily: the community as a whole has a strong feeling that at least one of the experiments must be wrong.
If you are just presenting a rival theory to someone else's in the sense of philosophy or the humanities -- i.e., the community as a whole will have no a priori problem with allowing the two theories to exist and each gain their own adherents -- then it seems to me that this is business as usual and everyone can read about it in the paper. But if you are working in a scientific, mathematical or other field in which the two works cannot coexist simultaneously in the community as a whole, then you are doing something that is potentially much more destructive to the other person. This doesn't mean that you shouldn't do it -- on the contrary, if anything you are more obligated to bring the issue to light -- but I think it would be at least courteous to personally contact the person whose work would be specifically invalidated by yours. On the other hand, whether something is "courteous" is clearly a matter of culture. I think that scientific fields vary widely on whether and how discourteous this practice is. For instance, there are some fields -- e.g. string theory -- in which large numbers of people are working within a very small and rapidly moving space. In this kind of situation, it is my understanding that you just take a good, rapid shot and see how everyone else reacts to it. If on Wednesday two contradictory string theory papers show up on the arxiv, then you know what people will be doing on Thursday: in other words, the community is so automatically and rapidly self-correcting that people think in terms of "good ideas that didn't pan out" rather
than "wrong papers". Or so is my understanding anyway: string theory is quite an amazing field to me because it is technically so similar but sociologically so different from my own.
In my field -- mathematics -- the culture regards my publishing a paper saying "Your paper is wrong" as an extreme act to be avoided at many costs. Much better would be for you to publish an erratum/corrigendum/retraction saying "Unfortunately the result I stated before is wrong; I thank [you] for bringing this to my attention." Publishing a paper -- or even circulating a preprint, say on the arxiv -- saying that Author X's work without making any attempt to contact Author X would be regarded by some as being discourteous to Author X. It could also be a strategically poor decision in some circumstances: when this happens, very likely some part of the community will mobilize to figure out "as a whole" who is right, you or Author X (or neither!). This mobilization will probably involve several people having conversations with both you and Author X, to the extent that you may end up talking to each other through other people. It could be more efficient and more seemly to have that conversation directly and privately with Author X. In particular, for better or for worse (and I think it is somewhat for worse) if you publish a paper saying "Author X is wrong" and you turn out to be wrong, then you may acquire a reputation for being a bit of a troublemaker.
Finally, in very technical fields, it is often the case that the unique person who is maximally well equipped to resolve the discrepancy between your work and Author X's is...Author X. So unless you have some reason to think otherwise, availing yourself of this resource sooner rather than later is probably a good idea.