Can I submit an extended version of a conference paper or a journal, if a better algorithm exists?
This is a perfectly normal timeline in theoretical computer science:


Result A is published in a conference.
Building on result A, someone else publishes followup work B in other conferences.
A polished version of result A is submitted to a journal and published there. The journal paper refers to result B and also discusses how follow-up work B has already improved on the results of the paper.


Here the fact that there is already follow-up work is a good sign that will help you to convince the reviewers that this is an important result that deserves to be published in a good journal.