Is a while loop with a nested for loop O(n) or O(n^2)?

Question

I have 2 blocks of code. One with a single while loop, and the second with a for loop inside the while loop. My professor is telling me that Option 1 has an algorithm complexity of O(n) and Option 2 has an algorithm complexity of O(n^2), however can't explain why that is, other than pointing to the nested for loops. I am confused because both perform the exact same number of calculations for any given size N, which doesn't seem to be indicative that they have different algorithm complexities.

I'd like to know:

a) if my professor is correct, and how they can boast the same calculations but have different big Os.

b) if my professor is incorrect and they are the same complexity, is it O(n) or O(n^2)? Why?

---

I've used inline comments denoted by '#' to note the computations. Packages to deliver should be N. Self.trucks is a list. self.isWorkDayComplete is a boolean determined by whether all packages have been delivered.

Option 1:

# initializes index for fake for loop
truck_index = 0   
while(not self.workDayCompleted):
    # checks if truck index has reached end of self.trucks list
    if(truck_index != len(self.trucks)): 
        # does X amount of calculations required for delivery of truck's packages
        while(not self.trucks[truck_index].isEmpty()):
            trucks[truck_index].travel()
            trucks[truck_index].deliverPackage() 
        if(hub.packagesExist()):
            truck[truck_index].travelToHub()
            truck[truck_index].loadPackages()
        # increments index
        truck_index += 1 
    else:
        # resets index to 0 for next iteration set through truck list
        truck_index = 0 
        # does X amount of calculations required for while loop condition
        self.workDayCompleted = isWorkDayCompleted() 

Option 2:

while(not self.workDayCompleted):
    # initializes index (i)
    # each iteration checks if truck index has reached end of self.trucks list
    # increments index
    for i in range(len(trucks)):   
        # does X amount of calculations required for Delivery of truck's packages
        while(not self.trucks[i].isEmpty()):
            trucks[i].travel()
            trucks[i].deliverPackage()
        if(hub.packagesExist()):
            truck[i].travelToHub()
            truck[i].loadPackages()  
    # does X amount of calculations required for while loop condition
    self.workDayCompleted = isWorkDayCompleted() 

Any help is greatly appreciated, thank you!

Answer 1

It certainly seems like these two pieces of code are effectively implementing the same algorithm (i.e. deliver a package with each truck, then check to see if the work day is completed, repeat until the work day is completed). From this perspective you're right to be skeptical.

The question becomes: are they O(n) or O(n²)? As you've described it, this is impossible to determine because we don't know what the conditions are for the work day being completed. Is it related to the amount of work that has been done by the trucks? Without that information we have no ability to reason about when the outer loop exits. For all we know the condition is that each truck must deliver 2ⁿ packages and the complexity is actually O(n 2ⁿ).

So if your professor is right, my only guess is that there's a difference between the implementations of isWorkDayCompleted() between the two options. Barring something like that, though, the two options should have the same complexity.

Regardless, when it comes to problems like this it is always important to make sure that you're both talking about the same things:

1. What n means (presumably the number of trucks)
2. What you're counting (presumably the number of deliveries and maybe also the checks for the work day being done)
3. What the end state is (this is the red flag for me -- the work day being completed needs better defined)

---

Subsequent edits lead me to believe both of these options are O(n), since they ultimately perform one or two "travel" operations per package, depending on the number of trucks and their capacity. Given this, I think the answer to your core question (do those different control structures result in different complexity analysis) is no, they don't.

It also seems unlikely that the internals are affecting the code complexity in some important way, so my advice would be to get back together with your professor and see if they can expand on their thoughts. It very well might be that this was an oversight on their part or that they were trying to make a more subtle point about how some of the component you're using were implemented.

If you get their explanation and there is something more complex going on that you still have trouble understanding, that should probably be a separate question (perhaps linked to this one).