0
$\begingroup$

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."

Algorithm 1

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

Algorithm 2

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.

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

1 Answer 1

0
$\begingroup$

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 !=.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.