What is the time and space complexity of this algorithm?

Question

What are the time and space complexity of this algorithm?

I calculate the WC time complexity to be as follow:

1. all initiations to be O(1) each

2. for loop to be O(n)because

   • outer for loop to run max of n times,
   • initiations to be cost of 1 each,
   • inner for loop to run max of 17 times, and
   • the if statements and assignments to be cost of 1 each.
   • I calculate O((n+1+1)*(17+1+1+1+1+1+1+1+1+1+1+1+1) then ignoring the constant O(n).

3. time complexity of the second part of the algorithm to be as follow:

   • Initiation of List to be of cost 1
   • for loop to be 17
   • Initiation of Meeting to be of cost 1
   • if statement to be of cost 1
   • initiation of indexOfEndTime to be 1
   • for loop to be 16
   • if statement to be 1
   • assignment to be 1 each
   • O(1+(17+1+1+1+1+1+1)*(16+1+1+1+1)+1) which is just constant value say c.

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

Is this correct? Could you please confirm if my every calculation was correct? In this case, the best case time complexity will be O(1)? Does it make sense to consider the average case and if it does how to figure that out?

Lastly, I calculate the best/average/worst space complexity to be 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;
    }

Answer 1

Your worst-case analysis seems to be completely correct; I didn't notice any mistakes in it, and I get the same result.

Your best-case analysis is incorrect; you said it takes O(1) time in the best case, but your loop over the meetings list always completes n iterations, so this case also takes O(n) time. You might have made the mistake of assuming that the list length is 1 or even 0 in the best case; that doesn't count as a "case" because you need to consider a family of inputs parameterised by the size n for asymptotic analysis to make sense at all.

Your space complexity analysis is not correct either. Your algorithm creates two data structures: the slots array has a constant size, and the condRange list also happens to have constant size because it is only appended to from the third loop, which we've established does O(1) operations, so the number of add operations to that list is also O(1). Even if this list did end up with a size of O(n), it is the output to the algorithm so any correct algorithm would have to create a list of that size; normally it's more useful to measure the "auxiliary" space complexity, i.e. the space used by temporary data structures which only exist for the algorithm's internal workings.

There is one assumption which would be useful to state explicitly, which is that the meeting startTime and endTime are always bounded in the range 0 to 16 (inclusive), so that it makes sense to use as an index in slots. By the way, you don't need to invent a name for the constant c, you can just write O(1) there.