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.
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!