Search code examples
algorithmstacktime-complexitycomplexity-theory

Is it correct to express algorithms' complexity with min or max operators?

I have an algorithm that creates an intersection of two ordered stacks of different sizes in another stack. That stack should be ordered as well. The size of the first one is n, the size of the other one is m.

while not empty(S1) and not empty(s2)
   //checks and possibly adds top element of S1 or S2 to S3, removes 
   //top element from only one of the stacks or from both if equal

I know that in the best case this algorithm has Θ(min(m, n)) complexity. Is it correct to express this complexity this way or should I only use operators like +,-,/,* etc? I mean something like O(m + n).

Should I consider the fact that one of the stacks can be smaller? Do we usually do this when calcuating the complexity of an algorithm?

Solution

  • Yes, you can use it.

    Also you might find useful this link