-1

What would be the Big-O for the following function?

for a in range(n):
        for b in range(n - a):
            for c in range(n - b):
                if a + b + c == 0:
                    break
            if a + b == 0:
                break
        if a == 0:
            break
    return n + 1

I was thinking that it would be O(N^3) since there is a triple nested for loop and each of the components of the for loop would have a Big O of O(N). Is my thinking correct or is there possibly a different Big-O for this function?

dataviz
  • 3
  • 1
  • 1
    Every loop breaks in the first iteration, so O(1) – Pranav Hosangadi Sep 23 '20 at 22:03
  • actually the innermost loop breaks first, so yes, O(1). But the indentation needs to be fixed – Walter Tross Sep 23 '20 at 22:05
  • 1
    This function is quite useless. Are you sure this is actually the code you meant to ask about? – DeepSpace Sep 23 '20 at 22:10
  • Very simply, you trace through the code to see how it works; pay special attention to how many times each statement will execute, expressed as a function of `n`. "Big O" is (basically) the limit of that function as `n` approaches infinity. – Prune Sep 23 '20 at 22:19

1 Answers1

3

This one is O(1). It's not because of the loops, it's because of the logic. Look closely at the range values. The Range function, when used with a single parameter, gives you a range object which functions somewhat like a list [0, ..., n]. For each loop there, the first value that each a, b, and c have will always be 0. So you'll always hit that a+b+c==0 break.

I'm guessing this is for a homework assignment? You can always try running it yourself a few times, just to see what the output looks like. Modifying the code to do something like the below might give you a decent idea of what's going on inside the function.

def sample_func(n):
    total = 0
    for a in range(n):
        for b in range(n - a):
            for c in range(n - b):
                total += 1
                if a + b + c == 0:
                    break
            if a + b == 0:
                break
        if a == 0:
            break
    print( total)
    return n + 1

for i in range(20):
    sample_func(i)
Garrett Patterson
  • 46
  • 3