Don't know what that complexity is about.
The question says that TM halts on every input i.e it outputs Yes for all strings belonging to L and NO for those that doesn't.
It implies its a halting TM which accepts Recursive language. (Recursive is superset of CFL and CSL).
For Recursively Enumerable languages, TM halts for acceptable strings but doesn't halt always if string doesn't belong to L and goes into infinite looping.
So answer is Recursive language
