(Text version)

function BALANCED( L: LIST ): boolean; { BALANCED verifies whether L consists of balanced parentheses } var S: STACK; p: position; begin MAKENULL(S); p:=FIRST(L); while pEND(L) do begin if RETRIEVE(p,L)='(' then PUSH('(',S) else if EMPTY(S) then return (false) else POP(S); p:=NEXT(p,L) end; return (EMPTY(S)) end; { BALANCED }

( A ) What is the computational complexity of the operation BALANCED expressed in terms of the size of the input? Assume that lists are implemented with pointers, that operations FIRST, NEXT and RETRIEVE take constant time, and that stacks are implemented with lists. Your estimate should be tight, i.e. the time spent on the execution of the operation BALANCED should be both big oh and big omega of your function. Provide justification with your answer.

( B ) Assume that in Problem A lists are implemented with arrays. What is the computational complexity of the operation BALANCED in this case? Provide justification.

Thank you for your help.

function BALANCED(L: LIST): boolean BALANCED verifies whether L consists of balanced parentheses ] var S: STACK; p: position; begin MAKENULL(S) p-FIRST(L) while pEND(L) do begin if RETRIEVE (p.L)F' then PUSH(CS) else if EMPTY(S) then return (false) else POP(S) p: NEXT(p,L) end return (EMPTY(S)) end, {BALANCED function BALANCED(L: LIST): boolean BALANCED verifies whether L consists of balanced parentheses ] var S: STACK; p: position; begin MAKENULL(S) p-FIRST(L) while pEND(L) do begin if RETRIEVE (p.L)F' then PUSH(CS) else if EMPTY(S) then return (false) else POP(S) p: NEXT(p,L) end return (EMPTY(S)) end, {BALANCED