2
$\begingroup$

I am reading CLRS 3rd Ed, chapter 17.1 (Aggregate analysis pg453) and I came across this statement.

Let us analyze a sequence of n PUSH, POP, and MULTIPOP operations on an initially empty stack.

I am confused as in:

  1. Do the push, pop, and multipop cumulatively add up to n operations.
    (there is a total of n operations which consists of x pushes, y pops, and z multipops where x+y+z = n)
    or
  2. Are they talking about n push, n pop, and n multipop operations?
    or
  3. 1st operation(push, pop, Multipop), 2nd operation(push, pop, Multipop), ..., nth operation(push, pop, Multipop)

The question is does the statement from the book imply 1 or 2 or 3 or something I did not mention above. Thanks

$\endgroup$
2
  • 5
    $\begingroup$ I don't have the book with me so I am not posting this as an answer but in all likelihood $n$ refers to the number of operations and "pop, push and multipop" to the kind of operations, so number 1 of your suggestions. If the intended meaning was different the phrase would (probably) have a different structure. $\endgroup$
    – phan801
    Commented Nov 3, 2021 at 16:32
  • $\begingroup$ @phan801 thanks that makes sense. $\endgroup$ Commented Nov 3, 2021 at 19:12

1 Answer 1

4
$\begingroup$

As phan801 commented, the first interpretation, a sequence of $n$ operations, each of which is either push or pop or multipop, is correct.

Either one of the other two interpretations might stand a small chance without surrounding context or with a very different context. However, had it been the intended meaning, "the phrase would probably have a different structure", such as, "n push operations, n pop operations, and n multipop operations" or "n operations, each being a push operation followed by a pop operation followed by a multipop operation".

A strong indication of the actual meaning comes from the introductory sentence of this section, "17.1 Aggregate analysis".

In aggregate analysis, we show that for all $n$, a sequence of $n$ operations takes worst-case time $T(n)$ in total.

The interpretation 2 means three sequences of $n$ operations instead of "a sequence of $n$ operations".

The interpretation 3 could have been more possible if push-then-pop-then multipop is a reasonable combination. However, after push-then-pop, multipop operation will always be a non-operation, since the stack is assumed empty initially. There is nothing interesting to analyze for this interpretation. (Even if the stack is not empty initially, we would probably use "push-then-multipop" since we can combine a pop operation followed by a multipop operation into another multipop operation".) So this combination of three operations as one operation does not make much sense.

$\endgroup$
1
  • 2
    $\begingroup$ By the way, the first interpretation fits the ensuing discussion in the textbook perfectly. $\endgroup$
    – John L.
    Commented Nov 3, 2021 at 19:45

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.