Is an algorithm in pseudocode a reasonable way to establish complexity?
To state the obvious, you need to prove that the language is decided by some Turing machine that uses a logarithmic amount of space on its work tape.

Anything beyond that is a question of how rigorous the proof should be. A proof should be rigorous enough to convince an appropriately skeptical reader. How much skepticism is appropriate in a given situation?  Well, that's a largely social construct. If we were chatting during a coffee break at a complexity theory conference, I'd probably be convinced by "Oh, just use a couple of binary counters to remember how many $a$s and $b$s you've seen. The input has length $n$ so the counters only need $\log n$ bits each."  If I was marking your undergrad complexity theory exam, I'd expect rather more detail. For example, our conference chat didn't include the fact that the machine should reject if it finds an $a$ after the first $b$ and your pseudocode also misses this, so it accepts the string $aba\notin L$.

Expecting a full definition of the Turing machine is probably unreasonable. First, it would take a long time to produce. Second, and more importantly, it would be sufficiently complicated that it would be hard to verify that the Turing machine really does what you claim it does. A proof that is too complicated for anyone to understand isn't really a lot of use.  That being the case, you're pretty much going to have to use pseudocode. If I wanted to test that you could produce a formal description of a Turing machine, I'd use a simpler language, such as the strings with an even number of $a$s in them.

Is pseudocode on its own enough? Not quite. For example, you can't just invoke Church&ndash;Turing to convert your pseudocode into a Turing machine. Why not? Because Church&ndash;Turing preserves computability but not complexity. So, what does an answer need?  I would say the following.


Pseudocode for an algorithm.
If it's not obvious, a proof (with an appropriate level of rigour) that the pseudocode actually solves the required problem.
If it's not obvious, a proof (with an appropriate level of rigour) that the pseudocode can be converted into a Turing machine with the appropriate resource bounds.


Even if you think the two proofs are obvious, it's a good idea to write a sentence or two about them. Trying to explain as briefly as possibly why something is correct can often find bugs such as the $aba$ problem.