Consider a language A which takes an input length of n. A set of branching programs is taken in such a way that each branching program accepts exactly the strings in A of length. Now, the Merge-sort IS implemented as a circuit in which the input length of language A has taken as the nodes of the branching program. After recursively dividing the given inputs in to half, it is used to compare two bits. The total time taken here (to divide the inputs into equal halves iteratively) is.
Let the inputs beand the outputs be. Now, the action of the merge-sort algorithm can be mimicked on an array. It is implemented one step at position to be the n-input,-output sub-circuit. Now, a pass is implemented as the serial concatenation of steps, which has a size. Therefore, this gives a sizelocalid="1664265778497" .
Hence, it is said that the language A is in logarithmic space. In other words, the language A is in L.