CODEWITHSUNDEEP
time-complexity
anonymous_DGB
anonymous_DGB

Reputation: 1

Why is concat in a cirlcular array time complexity = to O(min{n1,n2} +1) and not just O(min{n1,n2})

I am trying to understand why the time complexity for concatenation in a circular array is given as O(min{n₁, n₂} + 1) instead of just O(min{n₁, n₂}). I understand that we copy the smaller list, which contributes O(min{n₁, n₂}), but what is the purpose of the additional +1 in the complexity formula? Is it due to pointer adjustments or some other operation? Could someone explain this extra step and why it is necessary in the final complexity calculation?

Upvotes: 0

Views: 30

Answers (1)

trincot
trincot

Reputation: 350996

This is typically done to avoid an expression that yields O(0), which would appear when one of the lists is empty. That O(0) -- where only one of the two list lengths is variable -- could give the impression that there is no work at all, not even a fixed amount of work (as if it is the empty algorithm). The +1 avoids this situation in that case. When neither list is empty there is no need for this, but it doesn't hurt either.

You could also express this as: O(max{1, min{n₁, n₂}})

But most would not find this ambiguity a real issue and just say O(min{n₁, n₂}), assuming the asymptotic complexity is intended where both lists lengths are unbounded.

Upvotes: 1

Related Questions