We (including my teacher) designed a new algorithm in computer science and my teacher proved that it is good enough about its time complexity, but I'm not sure about that and worry that the proof be wrong.
Could I submit it to a journal?
It is your responsibility, not the referees', to make sure that a published proof is correct.
The reviewers should make sure that the results have some merit; some check proofs line-by-line, and some merely check that the result is plausible and that the proof methodology looks sound. Sometimes errors slip by. Nevertheless, if the result later turns out wrong, your reputation is at stake, not the one of the reviewers.
So speak with your advisor and make sure that your proof is correct before you submit. It might be the case that the proof is correct and you just haven't grasped all the details because you have less experience. Or it might be the case that there is a flaw to address and correct, in which case you should act before submission.
It is not a good research mentality to think "We only have to
fool convince one or two referees", in my opinion.
You should not submit if you are not confident the proof is right. Why not trying to boost that confidence instead? Two strategies I can think about to do that:
Give a talk in your department where you explain the proof to your peers and to more experienced researchers. It doesn't need to be anything formal, it could be a seminar, a research group meeting, or even a reading group.
Publish a preprint instead (for example on the arXiv), or write a blog post. If you are lucky, another researcher who is interested in the result will comment on it.
In general, I am suggesting that you discuss the result with other people before you publish it. It may be that you will catch the mistakes (if any) yourself, just by getting the chance of discussing it with other people.
EDIT: As pointed out in the comments, the second suggestion applies or not according to the OP's level of confidence. Of course, I didn't mean people should use the arXiv users as oracles that check the correctness of their proofs. It is nevertheless, at least in my opinion, an intermediary step before publishing to a journal. And anyway, arXiv was just an example, what I really suggested is to publish it somewhere online in order to give it more visibility.
My first hypothesis is that all the authors have done their best to have correct proofs, and that the question was asked with honesty to get advice, in order to be published in a serious journal.
This being said, it is not uncommon "not to be sure", or "to be afraid proofs might be wrong". Indeed, the history of science is paved with significant published papers containing flawed proofs, sometimes quite small. This happens even in mathematics, as detailed in Widely accepted mathematical results that were later shown wrong?
If your proof is ok, great. If not, and the algorithm is interesting enough, options are:
If you are aware that the proof is wrong, you ought to correct it before submitting it.
Meanwile, there exits a huge business of poorly reviewed conferences and journals, that would publish anything with some fees, and a huge amount of retracted papers recently. This undermines the work of honest scholars.