Is it a bad idea to critique someone's paper in my first publication? I am currently facing a situation that I am not sure how to handle. 

Basically, there is this problem $A$. Problem $A$ has been a hot topic in the past $5$ years. Last year, a paper was published in a very reputable journal (IEEE Transactions on Information Theory) that proposed a new algorithm that consists of $2$ sub-algorithms, $A_1, A_2$ that are both used to solve the problem. Here is the caveat, Algorithm $A_1$ was shown to eventually converge without any run time gurantee (shown to converge with finite number of steps), while $A_2$ was shown to take $O(n^5)$. 

My paper is essentially replacing $A_1$ with a new algorithm which is guaranteed to terminate correctly in $O(n\log n)$, hence bringing the overall time complexity when combined with $A_2$ to $O(n^6\log n)$. 

So far, so good. I am fairly certain the paper can get accepted into the same journal since the new algorithm is highly non trivial and provides lots of new insight on the problem. However, 2 weeks ago, I was wrapping up everything and decided to give algorithm $A_2$ another read as well as its proofs. That's when I faced some problems. 

One of the proofs in that paper is faulty, beyond repair. The author did a very big jump, and I managed to come up with a counter example essentially showing that the theorem he "proved" is false. I tried to fix his algorithm, but I couldn't. So I tried approaching it from a new perspective using his method, and I managed to get a new algorithm that replaces the faulty $A_2$, but it ran in $O(n^6)$. 

Here is my problem, my advisor thinks I should definitely include this in my paper as I've essentially replaced both algorithms $A_1, A_2$. However, If I just say I have an $O(n^6)$ when there is an $O(n^5)$ known, its going to raise eye brows. The only way I can pass this is if I actually take jabs at $A_2$ and show that its actually wrong, but I feel that "attacking" a paper in my first publication is a really bad idea. 

Any ideas?

EDIT: Contacted the author and he acknowledged the mistake. He agreed to be mentioned in the new paper and he showed quite the interest in the $O(n\log n)$ algorithm. He also contacted IEEE Transactions to see if they can add a correcting note. This went way smoother than I thought it would. Thanks everyone!
I think the same standards apply, regardless of whether it's your 1st or 100th publication. If you think you've found a mistake in a published paper, a common courtesy is to first contact the paper's authors for a clarification, as Noam suggested in the comments. If the authors confirm that it's indeed a mistake, you can indicate that in the paper (cite it as "private communication"); this should make the review process smoother.

When pointing out people's mistakes in print, gentle understatement is a good practice. "There appears to be a mistake in the proof" should be gentle enough. Having a counterexample certainly helps.