Big Oh worst case analysis - if statement inside loop

QOTDIANA 0
Viewed 70

For the worst-case analysis of the code below I think it's O(n^2), however my prof states its O(n), arguing that the maximum amount of operations per element is 2 (one push and one pop).

  • Since its an if-statement, isn't it one or the other? How is it both push and pop?
  • If it's the "worst-case" why can we not argue first pushing n-1 elements, and then for the very last iteration looping through the entire stack, resulting in O(n^2)?
void foo (int n){
    Stack<int> stack = new Stack();

    i = 0;

    while (i < n) {
        int key = random int from 1 to n
        
        if (key is odd) 
            stack.push(key);
        else {
            j = 0;

            while (j < key and !stack.isEmpty()){
                stack.pop();

            j = j + 1;
        }

        i = i + 1;
    }
}
complexity-theory time-complexity big-o if-statement algorithm
4 Answers

The best case scenario here would be that every drawn random value is even. In this case, each iteration of the loop would just no-op. No items would be pushed to the stack or popped from the stack. In the worst case scenario, each drawn random value would be odd. In this case, each item would be pushed onto the stack.

In both best and worst case, the running time of the loop is O(n). However, in the worst case scenario, the loop would also need O(n) storage space for the stack.

Note that worst case behavior of drawing many odds followed by drawing an even does not change the loop complexity, which is still O(n).

Tim Biegeleisen0

This is a tricky question! Your professor is approaching the problem with a different paradigm than you are (which is sometimes helpful). Instead of thinking about this problem in terms of what the loops will do, it can be helpful to think about it in terms of how many times each element operated on will be "touched".

For this problem, you are going to "touch" n integers during the execution of the program -- these are the "elements" you are operating on. For each element, think about what your program can do with it. What do you think?

You can either push that element onto your stack OR you can pop it off, right?

Next, think about this question: Is it possible to push an element (an integer) that has already been on the stack back onto the stack?

The answer is no. Once an integer has been pushed onto the stack, the while loop will never return to that integer. The variable i always increments but never decrements.

So, for each element, of which there are n, you can at most push it onto the stack once and pop it off at most once. Asymptotically, that works out to O(n) complexity.

In the future, when you're working on figuring out a tricky problem like this one, try to see if changing your paradigm helps to figure it out. :)

jlittle220

Your teacher is absolutely right.

  • there are at most n pushes, so there cannot be more than n pops. This justifies O(n). [The "very last iteration looping through the stack" would result in just O(n).]

  • when an odd number is pushed, it can be later popped [in your own "very last" example, all elements but one could be pushed then popped].

Yves Daoust0

Apologies for contributing an answer with so many correct responses, but it might be easier to explain with a diagram. You are correct in your assessment of the worst-case, where the stack builds with odd numbers and finally as the last one n or n-1, an even number, causes the stack to empty completely. In this case, a rough diagram of the work done, vertical, per time on the horizontal for one n.

1 until the last, which is n

The maximum work per step is n, and there are n steps. It is true that the problem is in O(n^2). This corresponds to filling a square n x n: \sum_{t=1}^{n} n = n^2 \in O(n^2). Also your teacher is right; by splitting the work into two parts, you can achieve a tighter bound: sum_{t=1}^{n-1} 1 + n = n - 1 + n = 2n - 1 \in O(n).

Amortized analysis.

One might also ask what is the run-time of the inner loop? The worst-case is also O(n) because that one where the stack empties. Times n, is O(n^2). In amortized analysis, you look at a sequence of operations. Thus, you can borrow a from a high value to even it out. This is O(1) amortized per step.

userVjna0
Related