# Understanding time complexity of algorithm to determine if parenthesis are matching

Both these algorithms determine if all the parenthesis in a string are balanced and properly nested.

The first algorithm uses "a constant amount of memory, regardless of the length of the string."

The second algorithm "may use O(n) memory but must use a stack".

I understand how the algorithms work but I don't understand the descriptions of time complexity.

My understanding is that they are both O(n) because they both use a single for loop and the length of time it will take to execute them depends on the size of the string.

Also on algorithm 2 I believe the last bit should be if t!=0 instead of ==?

Any help understanding these descriptions of time complexity would be greatly appreciated. Thanks.

• – D.W.
Commented Apr 8, 2022 at 18:27
• What do you know about the time taken by s(i), t.push(), t.pop(), t.length? Commented Apr 9, 2022 at 6:50
• They run in O(1)? Commented Apr 9, 2022 at 18:43
• @BenHarris You have a pretty good understanding of time-complexity. It looks like you have no questions. Commented Apr 9, 2022 at 21:32
• I’m voting to close this question because OP has got all the right answers. No questions. Commented Apr 9, 2022 at 21:33

Both your algorithms have the same asymptotic running time $$O(n)$$, but they differ in their memory usage. The first algorithm uses only $$O(1)$$ auxiliary storage space (for example, the variable count is used). On the other hand, the second algorithm takes $$O(n)$$ extra storage, because in the worst-case, the input would be of the form $$(^{n/2} )^{n/2}$$, i.e. $$n/2$$ opening parantheses followed by $$n/2$$ closing parantheses, and the algorithm would have to store $$n/2 = O(n)$$ bytes on the stack.