Java – What is the temporal and spatial complexity of this algorithm?

What is the temporal and spatial complexity of this algorithm?

The WC time complexity I calculated is as follows:

1. All initializations are O(1).

2. The for loop is O(n) because

   • The outer for loop runs up to n times
   • Each initiation fee is 1,
   • The internal for loop runs up to 17 times, and
   • The if statement and the assignment cost 1 each.

   I calculate O((n+1+1)*(17+1+1+1+1+1+1+1+1+1+

   • 1+1+1) and then ignore the constant O(n).

3. The time complexity of the second part of the algorithm is as follows:

   • The cost of launching a List is 1
   • The for loop is 17
   • The starting fee for a session is 1
   • The cost of an if statement is 1
   • Initialize indexOfEndTime to 1
   • The for loop is 16
   • The if statement is 1
   • 1 per person is allocated

   O(1+(17+1+1+1+1+1+

   • 1)*(16+1+1+1+1)+1) is the constant value c.

T(n) = Step 1 + Step

4. 2 + Step 3 = O(1+n+c) which means my worst-case time complexity is O(n).

Is this correct? Can you confirm that each of my calculations is correct? In this case, the best time complexity is O(1)? Does it make sense to consider the average case? If it makes sense, how is it calculated?

Finally, I calculated that the best/average/worst space complexity is O(n).

    public static List<Meeting> mergeRanges(List<Meeting> meetings) {
        byte available = 0;
        byte reservedBlockStart = 1;
        byte reservedBlockMiddle = 2;
        byte reservedBlockEnd = 3;
        byte[] slots = new byte[17];

for(Meeting meeting : meetings) {
            byte startTime = (byte) meeting.getStartTime();
            byte endTime = (byte) meeting.getEndTime();
            for(byte i = startTime; i <= endTime; i++) {
                if(slots[i] == available) {
                    if(i == startTime) {
                        slots[i] = reservedBlockStart;
                    } else if(i == endTime) {
                        slots[i] = reservedBlockEnd;
                    } else {
                        slots[i] = reservedBlockMiddle;
                    }
                } else if(slots[i] == reservedBlockStart) {
                    if(i != startTime) {
                        slots[i] = reservedBlockMiddle;
                    }
                } else if(slots[i] == reservedBlockEnd) {
                    if(i != endTime) {
                        slots[i] = reservedBlockMiddle;
                    }
                }
            }
        }

List<Meeting> condRange = new ArrayList<Meeting>();
        for(byte i = 0; i < slots.length; i++) {
            Meeting meet = new Meeting(0,0);
            if(slots[i] == reservedBlockStart) {
                byte indexOfEndTime = i;
                meet.setStartTime(i);
                for(byte j = (byte)(i + 1); j < slots.length; j++) {
                    if(slots[j] == reservedBlockEnd) {
                        meet.setEndTime(j);
                        indexOfEndTime = j;
                        j = (byte)(slots.length - 2);
                    } 
                }
                condRange.add(meet);
                i = (byte)(indexOfEndTime - 1);
            }
        }
        return condRange;
    }

Your worst-case analysis seems entirely correct; I didn’t notice any errors in it and I got the same result.

Your best case studies are incorrect; You say that O(1) time is needed in the best case, but your loop on the meetings list always completes n iterations, so this case also requires O(n) time. You might mistakenly assume that the list length is 1 or even 0 in the best-case scenario; this doesn’t count as a “case” because you need to consider a set of inputs parameterized by size n to make the asymptotic analysis fully meaningful.

Your spatial complexity analysis is also incorrect. Your algorithm creates two data structures: the slots array has a constant size, and the condRange list also happens to have a constant size because it is only appended from the third loop, and we establish an O(1) operation, so the number of times an add operation is added to the list is also O(1). Even if this list ends up with a size of O(n), it is the output of the algorithm, so any correct algorithm must create a list of that size; In general, it is more useful to measure the “auxiliary” space complexity, that is, the space used only by temporary data structures that work inside the algorithm.

There is an assumption that needs to be made clear that session startTime and endTime are always limited to the range of 0 to 16 inclusive, so it makes sense to use them as indexes in slots. By the way, you don’t need to invent a name for the constant c, you can write O(1) there.