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.
1 Answer 1
Two algorithms can have the same (asymptotic) time complexity but differ in their space complexity. The amount of extra storage space consumed by the algorithm is another performance measure of the algorithm.
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.
Yes, the == should be !=.
Explore related questions
See similar questions with these tags.
s(i),t.push(),t.pop(),t.length? $\endgroup$