0

I am estimating the worst-case time complexity of this piece of code:

if (condition) {
  // loop over A
} else {
  // loop over B
}

such that A and B are disjoint sets and |A| + |B| = C. In my opinion, the worst-case time complexity is O(max(|A|, |B|)) = O(C). Could you please tell me if it is correct?

Also a side question, if I have a complexity like O(N(1 + M)), do I have the right to drop 1 and keep only O(NM) as the final complexity?

I apologize if my question is too basic. I haven't touched complexity analysis for a long time.

Thank you!

Elise Le
  • 5
  • For your first question, yes, worst-case would take O(max(A, B)), which is equal to O(A + B). For your second question, also yes, because O(fg) = O(f) O(g). – K. Jiang Feb 27 '23 at 15:33
  • For the first question max(A,B)=C (cardinals) only when either set A,B or both are empty. Therefore the correct answer is simply max(A,B). Second question is invalid given the context of if-block: you can’t assume a return to testing after leaving the block- that will require further information to assess how many times the return could happen. Neither one of your answers relates to the problem. Using your notation, the answer to both questions is max(|A|,|B|) – WindSoul Feb 27 '23 at 16:34
  • @WindSoul Sorry I didn't clarify but my second question is not related to the if-else block. It's just a complexity estimation for another case. – Elise Le Feb 27 '23 at 20:33
  • 1
    @K.Jiang Thanks for your reply! – Elise Le Feb 27 '23 at 20:33

1 Answers1

0

I am guessing that it may depend on the condition, and some probabilities of A and B hitting the condition. For example, if the condition is A.length > B.length then it would be O(max(|A|, |B|).

Also for your side question, you definitely can drop the N in the O(N(1+M)) to have the final be O(NM).

Aidan
  • 122
  • The condition is more complicated and doesn't directly relate to the characteristics of A or B. Actually, there's no strict guarantee, whether |A| > |B| depends a lot on the data. Maybe leaving it as max(|A|, |B|) is safer? – Elise Le Feb 27 '23 at 20:38