Mike Hostetler writes in this weblog entry that Java does not need to be slow when you use the -server jvm switch.
I once wrote an article for iX magazine about benchmarking Xslt processors. Here, the fastest one also was written in Java -- and I did not even experiment with the server jvm. My results are also backed by the results on the Java is faster than C benchmark page.
Also popular belief is that if you want to do fast database access, you have to do this in embedded sql (esql) within C. This might be true, if you have to go to the database for every record anyway, but if you are iterating over a known (sub)set of the data over and over again, it might be better to let your infrastructure (e.g application server or O/R manager cache the data).
And then last, but not least: Remeber that everything that can be done in O(n) can also be done in O(n²).