Can master's thesis be simply a description of an original algorithm? I'm in a situation where I've probably bitten off more than I can chew. I decided to do my master's thesis on an original (as in, invented by me) machine learning algorithm, which I believe (and my advisor agrees) is interesting and might have something to contribute to the academia.

As a part of the thesis I wanted to implement the algorithm. However, implementing it is turning out to be a major pain. I've been working on the implementation for several months and the end is still nowhere in sight. Due to this, I'd like to change my thesis to be simply a description about the algorithm and comparison of it to existing, similar algorithms.

So my question is, is it feasible to have an original, unproven and untested idea as the main focus of your thesis? This feels iffy to me: master's thesis is supposed to be a sign of academic maturity, but nothing seems more unacademic to me than publishing an untested and unproven idea in the form of thesis, and not even having a working implementation of it.

I'd really appreciate advise, dragging this thesis is really getting the better of me. Thanks.
Write a chapter of your thesis in the shape of a review paper, which is good enough to submit for publication. Submit it. Write another chapter which builds on the review and uses that as an argument for the derivation of a new algorithm. Present the algorithm. In the discussion, highlight the steps needed to implement the algorithm and point out the problems encountered when you tried implementing it yourself. That's a MSc for me.