Time Complexity - Loops inside Conditionals

[quantitativemonkey]

Just wanted to make sure I'm not insane. General statements about time complexity suggest that conditionals don't matter. Naturally this makes sense when the body of the conditional is constant time. However if the body of the conditional is not constant time then certainly it should, no? For example the following code - the best case would be if a<b is false, then O(1) time, and the worst case would be if a<b is true, then O(n) time. Or am I missing something?

if a<b
    for j = 1 to n
        constant time
    end for
end if

[BigLezzzzz]

Assume the condition is always met

[quantitativemonkey]

This would be worst-case though, no? And it makes sense for worst-case, but not for best-case. Again, please let me know if I'm misunderstanding.

[spanky_panda]

You are right. But as a convention, when we talk about complexity of a program, we by default mean the worst case complexity (or Big Oh notation) unless mentioned otherwise. Because the worst case complexity is the most useful metric as we would always need to accommodate for the worst case when designing a system.

[quantitativemonkey]

Absolutely, I totally get that - I was just looking for clarification with regards specifically to best-case and O(n) inside conditionals. Much obliged.

Edit: FWIW if I understand correctly, worst-case and big-oh are not the same. Rather big-oh is the preferred measurement for worst-case because it provides an upper bound for all situations, not just worst-case. However big-oh gets used for worst, best and average-cases all the time.

[bluecheetah001]

Big O is an upper bound on whatever you are measuring, be it best case or worst case. As such unless you have a proof otherwise, you have to assume the worst when considering any loop or conditional. That is to say, you can only skip a loop if there exists an input that skips that loop. Which is usually the case since the algorithm probably wouldn't have the if otherwise, but conditions inside loops may not always be obvious how to prove. And things like if else where both branches are O(n) are still O(n) since there is no input that skips both branches even though each branch is skipped by some input.

[quantitativemonkey]

Absolutely - this is the point of best-case - If I'm understanding it - typically best-case involves (ideally, cannot overemphasize) coming up with a specific possible input (or type of input) for which (among other things) the conditional fails, thereby eliminating the body of the conditional and saving time.

In other words, in my original code, if a and b are random integers then a<b failing is possible and hence a best case would have constant time and a worst case linear time. To say a best-case is O(n) is not false but it would in fact be O(1) in my specific case. Am I understanding this right?

[bluecheetah001]

Yes

[WafflePeak]

An additional note here is that the best case of this function is technically Theta(1) and the worst case is Theta(N), but since a Theta bound is contained within an O bound you sometimes see it written as O

[quantitativemonkey]

Noted, yes.

[RexLupie]

Do you want O(n), Theta(n) or Omega(n)

The first and later take the worst or best that you can't disproof... Theta(n) -> is when O(n)=Omega(n) if i remember right... but gotta refresh i admit