CODEWITHSUNDEEP
stacktime-complexity
user7374120
user7374120

Reputation: 1

Time complexity for iteration over a stack

I have an array of objects, and I have two stacks i go over the array and for every elemment i push the previous objects (pop from stack 1 and push to stack 2) and then resotre them (pop from stack2 and push to stack 1).

I wonder what time complexting it is - o(n) or o(n^2)

because every stack operation (push pop) is o(1).

 for (int i = 0; i < buildingsHeight.Length; i++)
            {
            
                while (!BuildingStack.IsEmpty() && !didWeFoundHigerBuilding)
                {
                   
                    BuildingStackNode buildingInLine = BuildingStack.Pop();
                    
                    helperStack.Push(BuildingStack.Pop());
                }

                // restore data 
                while (!helperStack.IsEmpty())
                {
                    BuildingStack.Push(helperStack.Pop());
                }
}

Upvotes: 0

Views: 186

Answers (1)

Mo B.
Mo B.

Reputation: 5815

First of all, I suppose you mean "O" and not little "o" (which has a different meaning)? Secondly, saying something like O(n) doesn't make any sense without defining "n". So what is n?

The code you showed is a bit strange in that you are looping over the array buildingsHeight but you are not doing anything with the array within the loop. Anyway, the time complexity of this piece of code depends on two parameters: the length of buildingsHeight a and the number b of items in BuildingStack (assuming that helperStack is initially empty).

The while loops each take O(b), and the for loop iterates a times, so the overall complexity is O(ab).

Upvotes: 1

Related Questions