Can I publish an algorithm without time complexity?
An algorithm that solves a problem in a new way is interesting, regardless of whether you beat the state-of-the-art, because that new way might start a new line of research that beats the state-of-the-art. But, as it stands, you seem unaware of where your algorithm ranks and establishing that is highly desirable (perhaps even necessary) prior to publication. Thus, although it might be possible to publish now, it seems better to delay publication to establish your algorithm's ranking.