newbiez newbiez - 4 years ago 437
Python Question

Time Complexity of nested if, compared to multiple cases in while

I am looking at the time complexity of various solutions, and since I am not much of a math lover; I can't quite figure out the best time complexity for my call.

The problem is that I am not sure if it takes longer to get trough a while loop with 1 statement, and nested if-else, or if it is better to remove the nested if-else and add the check in the while loop.

As generic example would this perform faster

while a>1 and b is True
if x is True:
a -= 1
else
a += 1


instead than

while a>1:
if x is True:
if b is True:
a -= 1
else:
a += 1


I recall that nested if result in O(N^2), while a simple while loop has complexity O(n), but what happens when the while loop has to check multiple statements.

Answer Source

I recall that nested if result in O(N^2)

Wrong, a nested for loop has a complexity of O(N^2) not an if.

If you have an array of size N and you do

for i in arr:
    for j in arr:
        print "hello"

How many times will you see "hello" printed? N^2, which is the complexity.

Note that it doesn't matter what you doing inside your loops (whether you are printing, adding, doing an if statement), that is all a fixed cost. And so the fact that you are re-arranging your if statements doesnt matter - both cases have the exact same complexity.

What matters is how often that "body" of code inside your while loop is executed, and that's what determines the complexity.

So let's because both of your examples have the same complexity, let's break down the first one:

while a>1 and b is True
    if x is True:
        a -= 1
    else
        a += 1

b appears to be an independent variable, so we should be able to ignore that. if x is True, your time complexity is infinity, since the while loop will never end (this means your statement "while loop has complexity O(n)" is also wrong). If x is False, your code has a time complexity of O(a-1) (or simply O(a)), since it will run through a-1 iterations.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download