This is a question best addressed to your adviser or someone else familiar with your work, because questions like these often depend on the details of what you're doing.
It depends on the subfield, the nature of the work, and what evidence you can provide that the methodology. You need to provide argumentative evidence that your approach is noteworthy and correct. This can be a mathematical proof of correctness, a diagram and five pages of discussion and commentary, or a statistical analysis comparing the algorithm to other similar ones. Which is most appropriate depends on the nature of your work. However, whatever you choose is going to be an involved endeavor, and you have little hope of getting something published if you insist on not doing a meaningful evaluation of its performance.
Assuming that you are willing to evaluate and validate your algorithm, but just not willing or able to implement it...
If you're doing theoretical work, the answer is likely "yes you can publish it". New algorithms for known problems or improvements to the theoretical run-times of established algorithms are often published with formal proofs of correctness rather than implementations. Pseudo-code would be encouraged but is not even always necessary.
If you're doing non-theoretical work, the answer is likely "no you cannot publish it". Non-theoretical CS work of this type is usually backed by numerical experimentation and quantitative comparison to known benchmarks and frequently-used algorithms. In an ideal world, you'd even leverage statistics to improve your analysis.