Big Oh worst case analysis - if statement inside loop-CodePudding

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;
}
}

CodePudding user response：

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

CodePudding user response：

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. :)