Would I be correct in assuming this function runs in linear (O(n)) time?-CodePudding

Here is a function I wrote in pseudo code:

partition(itemList) {
    numPackets = calculateNumOfPackets(listSize, packetSize); 
    indexOfNextItem = 0; 
    packetQueue = initialize(numPackets); 
    for (i = 0; < numPackets; i  ) {
        // Initialized as a fixed-size list 
        Packet p = createNew(packetSize); 
        for (j = indexOfNextItem; j < itemList.length; j  ) {
           // hasRoom() returns false when packet is at capacity
            if (p.hasRoom()) 
                // Guaranteed to run in constant time due to predefined capacity
                p.add(item[j]); 
            else {
                indexOfNextItem = j; // keep track of next index for inner loop
                break; 
            }   
        } // end inner
        packetQueue.add(p); 
    } // end outer
    return packetQueue; 
}

As I hope is clear, this just does partitioning and returns a partitioned queue of "packets" that contains the items of the input list. Now I'm pretty sure this is running in linear time because the inner loop isn't running fully for each iteration of the outer loop; it's only running until the current packet is full, at which point it keeps a cache of the index where it left off and then breaks out of the inner loop. As a result I suspect this is actually running in linear time.

Am I understanding this correctly?

CodePudding user response：

If createNew(packetSize) is linear in packetSize, initialize(numPackets) is linear in numPackets and all of p.hasRoom(), p.add(), itemList[i] and packetQueue.add(p) are O(1), your algorithm is O(listSize) (assuming listSize is len(itemList).

The sketch of the proof is that each inner loop will execute at most packetSize O(1) operations, and that inner loop will be executed at most ceil(listSize / packetSize), thus the total number of operations will run at most (numPackets 1) * packetSize * n, where n is a constant related to the number of operations done in each loop.

CodePudding user response：

One of your comments states that:

Given a list of items, the algorithm is supposed to add a certain number of these items to packets (represented as fixed-size lists) and returns a queue of said packets. So if the input list had 100 items, and the max packet capacity allowed is 10, then you'd get a queue of 10 packets each having 10 items.

If this is true, then, since each item is only included in 1 packet, your algorithm is linear in the number of items (O(itemList.length)) - assuming that placing items into packets is constant-time.

Counting nested loops only makes sense if the loop counters are independent. If you know that, as in this case, every item in a list is being visited once and only once, and that visit is constant-time, you can confidently state that such code is linear in the number of items.