[Incorrect Solution]

[JoseCutileiro]

Qual a UC que tem a resolução incorreta?

(TC) Teoria da Computação

Em que ficha/capítulo/exercício/passo se encontra o erro?

1 - > 5

O que está incorreto e qual é a resposta certa?

Não é nada de grave mas é útil relembrar:

Repara que a MT do enunciado usa bilateralidade. Assim provas que L pertence a O((nlogn)^2). Para provares que L pertence a O(nlogn) basta fazeres uma composição de máquinas com a MT que eles te dão e outra que faz um SHR. E depois basta relembrares que a MT que faz o SHR tem complexidade linear e então O(n)+O(nlogn) vai estar ainda em O(nlogn).